For simplicity, consider only functions from $\Bbb N$ to $\Bbb R^{>0}$. Let $f\preceq g$ if there is an $A>0$ such that for all sufficiently large $n$, $f(n)\le A g(n)$. We normally would write this $f\in O(g)$, but I want to emphasize the order properties in this post.
This is a preorder on the space of functions, so we can quotient out by the equivalence class $f\sim g\iff (f\preceq g)\land (f\succeq g)$ to get a partial order. It is also a lattice, with $f\lor g\sim \max(f,g)\sim f+g$. It even has an abelian group structure (multiplication of functions) that respects the order, with $f\preceq g\iff f/g\preceq 1$.
But it is not a total order; any function both unbounded above and below, such as $f(n)=\begin{cases}n&n\mbox{ even}\\1/n&n\mbox{ odd}\end{cases}$, is incomparable to $1$. In fact, this kind of "oscillation" between different orders is necessary for incomparability to occur, although it may still occur in monotonic functions, simply by multiplying by a sufficiently fast-growing function, such as $n^{2n}$ (that is, $n^{2n}$ is incomparable with $n^{2n}f(n)$ even though $n^{2n}f(n)$ is monotonic).
My question is, why is it that we can basically ignore this fact completely when discussing orders of common functions? Given an arbitrary function, we seem to have some method for choosing "simpler" functions which are drawn from some chain $S$. So for example the function $f(n)$ above would generally only be compared as $1/n\preceq f\preceq n$, where $1/n$ and $n$ are members of this $S$.
But what is $S$? Desirable properties for $S$:
- $S$ is a chain, i.e. $f\preceq g$ or $f\succeq g$ when $f,g\in S$
- $n\in S$
- $S$ is a subgroup and a sublattice, i.e. $f,g\in S\implies f/g,f+g\in S$
- $S$ is closed under $\log$
- $S$ is closed under $\exp$ (note: $\exp$ is not well-defined on equivalence classes)
Does such an $S$ satisfying the properties actually exist? The toughest restriction is (5); most of the others play well with the total order constraint. I think this covers all the functions I have seen in an asymptotic expression, not counting multivariate expressions like $O(mn)$ or composite expressions like $e^{n^2+O(n)}$. Exceptions include $\log^*(n)$ and fast growing functions like the Ackermann function.