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.
Why the bound of a linear function is same as that of a quadratic equation
algorithms;complexity
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.