# Does big-Oh impose an ordered partition on the set of the "usual" functions?

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.

• $2n = O(n)$ but also $n=O(2n)$... Jun 24 '20 at 23:18
• @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. Jun 25 '20 at 6:26