Well, when we use Big O notation we never know even approximate number of steps of a given algorithm, right? For example, if we have $O(n)$ algorithm, then we don't know how fast this algorithm itself is: its exact number of steps may be $10n$ or even $10^{100}n$. Thus we just put this algorithm in particular "class of functions" $O(n)$.
The reason for doing that is for us to be able to compare algorithms from different "classes". For example, we always know that $O(n)$ is going to be slower than $O(\log_2 n)$ for large $n$, because $\lim_{n \to +\infty} \frac{\log_2 n}{n} = 0$.
But if we are told that there are two different $O(n)$ algorithms, then we can't say which one is going to be faster, right? Moreover, if we are given a single $O(n)$ algorithm, we can't say how fast it is (because it may take $10n$ or even $10^{100}n$ steps and still be $O(n)$).
Is it the main and the only idea behind Big O notation? Or is there something else that I missed?
I've already googled it million times and still have this confusion in my head. So, please, check my understanding and say if anything is wrong. Thanks in advance!
Best Answer
Yes, this is correct. My late PhD supervisor disliked using these notions for this very reason. A smaller $O(n)$ class means that, for sufficiently complex inputs, the algorithm will be faster, but there's no guarantee how big $n$ would have to be in order to see a difference.
As a concrete example, the AKS primality test showed that primality testing could be done in polynomial time. This is, of course, an impressive achievement in computer science and pure number theory. In practical terms, you're better off using other algorithms, despite the fact that they do not terminate in polynomial time.