Teaching an algorithms course recently, I realized that the correct use of these asymptotic notations is apparently rather difficult for students to grasp. In fact, I have some colleagues whose understanding of these concepts is not maximally clear.

In 1976 Donald Knuth published an article explaining these notations in detail and recommending their use. After 35 years and plenty of evidence that it works well, we still have resistance. Perhaps one reason is that the idea of “asymptotically equivalent to”, or “of the exact order of”  is formalized by the symbol Theta, while O is a simpler and more familiar symbol that evokes the word “order”. The most common misuse I have seen is exactly this use of O when Theta is meant. The principle that the most important and useful concepts should have the simplest notation implies that O would be better for computer science use. However, that would make it inconsistent with mathematical use where big-O is definitely used for upper bounds only.

The main mistake seen (also mentioned by Knuth) apart from the perhaps excusable one above is not excusable: it is the use of O to discuss lower bounds as in the example: “Algorithm A is better than Algorithm B because A is known to  run in time O(n log n) and B in time O(n^2)”. If O is replaced by Theta, then this might make sense, but the literature is full of algorithms whose O-bounds are not asymptotically tight – how do we know B doesn’t run in time O(n) also? Again, if you think that O means Theta, this mistake is an easy one to make.