The example in this answer proves the fact familiar to CS students - that the "big-O" is not a total order. However, most algorithm running times analyzed using big-Oh notation are not expressed in piecewise form like this example. In fact, most algorithms I am familiar with have a running time expressed in terms of polynomials, exponentiations and logs.

Consider the recursively defined class of functions which includes $f(n) = c$ for any constant $c$, $f(n) = n$, and any functions of the form $f + g, f \cdot g, \log(f), \exp(f)$ where $f,g$ are in the class. Does $O$ impose an ordered partition on this class of functions? The functions with the same big-$O$ growth is in the same part.

Here are my thoughts:

Note that specifying $f \cdot g$ is actually redundant, since $f \cdot g = \exp(\log(f) + \log(g))$. Since the functions are inductively defined, perhaps there is an inductive proof.

  • 1
    $\begingroup$ $2n = O(n)$ but also $n=O(2n)$... $\endgroup$
    – nir shahar
    Jun 24 '20 at 23:18
  • 2
    $\begingroup$ @nir Yeah, you need to replace "total ordering" with "weak ordering" for this question to make sense. Here's a Scott Aaronson proof of a related theorem on O notation classes. I think I might have seen more about this from him somewhere. $\endgroup$ Jun 25 '20 at 6:26

This was shown by Hardy in his monograph Orders of Infinity.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.