Everyone who reads or writes about the complexity of the algorithms must know for sure that the Landau Symbols and asymptotic notation , otherwise they really do not understand what is happening, or simply have an approximate (and often misleading) idea.
To simplify (a lot), let f and g be two functions of f : N -> N and g : N -> N We say that f is O(g) if and only if there exists a constant M > 0 such that |f(n)| < M|g(n)| |f(n)| < M|g(n)| for all n > M That is, more informally, starting with a large value of n , all values of f(n) less than a multiple of g(n) (i.e., g grows faster than f ).
This definition is equivalent to
f is O(g) <==> There is K >= 0 such that lim{n -> +oo} |f(n)|/|g(n)| = K
So, take f(n) = 4n^2 + 7n and g(n) = n^2 and try to prove f is O(g) (I omit {n -> +oo} ):
lim |f(n)|/|g(n)| = lim f(n)/g(n) = lim (4n^2 + 7n) / n^2 = 4 + lim 7n/n^2 = = 4 + lim 7/n = 4 + 0 = 4
It follows that there exists M such that n > M ==> |f(n)| < M|g(n)| n > M ==> |f(n)| < M|g(n)| and therefore f is O(g) .
So it’s technically correct to say 4n^2 + 7n is O(4n^2) , since it’s right to say 4n^2 + 7n is O(n^3) , 4n^2 + 7n is O(e^n) and so on. But to be meaningful, we are interested in the lower bound. Therefore, if f is O(e^n) and f is O(n^2) , we are more interested in knowing that f is O(n^2) , since this is much more restrictive.
VERY IMPORTANT note
What is especially important when choosing an algorithm is to understand that the big-O notation refers to asymptotic cases, that is, when you consider extremely unimaginable huge inputs that can go far beyond the computational power available in a known universe (i.e. infinite input sets expressed mathematically with {n -> +oo} ).
For practical use (i.e., not very large inputs) when choosing an algorithm, of course, you will observe algorithms of a large number of applications with candidate algorithms, but you must be sure that the selected algorithm is well adapted (and works better) for your (expected ) input.
Finally, usually more efficient algorithms are more difficult to understand and implement correctly. You should also take this fact into account when choosing an algorithm (i.e., this is the time that I will spend debugging and fixing my implementation of this algorithm, significantly exceeding the time I will have to wait with another algorithm, with worse than the note "big O "? If so, you should consider a simpler and less efficient algorithm, since the overall solution will be more efficient).