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.
It is important to realize, that
Just like there is more than one number that is bigger than
The tightest bound for
I suggest you take a look at this similar question for more information.
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(n2), or O(n3), or O(n4), or O(en).
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.