Why the bound of a linear function is same as that of a quadratic equation

Question

I am learning algorithms, and I came across something very interesting.

The asymptotic bound of the linear equation (a * n)+b is O(n^2), for all a > 0.

This is same bound as a * n^2 + b * n + c, which is surprising.

Answer 1

It is important to realize, that O(f) represents a set of functions, for which c*f is an asymptotic upper bound for some constant c.

Just like there is more than one number that is bigger than 1, there is not just a single function that qualifies as an asymptotic upper bound for a function.

The tightest bound for (a*n) + b) is O(n), but it is also in O(n^2), but that's being very generous, and doesn't provide as much information as saying it's in O(n), because that is a much stronger statement.

I suggest you take a look at this similar question for more information.

Answer 2

Roughly speaking any two functions can be bounded by the same bound. The thing we really care is whether the bound is tight or loose. any constant O(1), linear and quadratic functions can be surely bounded by O(n²), or O(n³), or O(n⁴), or O(eⁿ).

But considering a very loose bound really can't give much information about a function itself. Thus, in practice, we should always choose the tightest bound for a function. So usually, when we talk about the bound, it could implicitly be the tightest bound.