# Natural class of functions whose $\mathcal O$-sets are linearly ordered

In doing complexity analysis of algorithms, we often restrict to their asymptotic complexity. A function $g: \mathbb N \to \mathbb R_+$ is asymptotically bounded by $f: \mathbb N \to \mathbb R_+$ if there are constants $c \in \mathbb R_+, N \in \mathbb N$ such that for each $n \geq N$, $$g(n) \leq c\cdot f(n).$$ The set of all such $g$ is referred to as $\mathcal O(f)$. By letting $g \preceq f$ if $\mathcal O(g) \subseteq \mathcal O(f)$, we obtain a preordering on the set of functions $\mathbb N \to \mathbb R_+$.

Examples of functions that typically come up as complexities of algorithms are: $$\tag{*} \log(\log(n)), \log(n),\log(n)^2, \sqrt{n}, n, n\log(n),n\sqrt{n},n^3, 2^n, 3^n, 2^{2^n}.$$ Interestingly, these functions are all linearly ordered by $\preceq$. Note that it is not hard to find functions which are not linearly ordered by $\preceq$, like $|\sin(n)|$ and $|\cos(n)|$, and with some fiddling it would not be too hard to make examples of strictly increasing (or even convex) functions which are not linearly ordered by $\preceq$. However, these examples all seem artificial, and in particular I would be surprised if they ever came up as complexities of algorithms.

Can we explicitly give a nice class of functions that includes at least all the functions listed in (*), and for which $\preceq$ is a linear ordering? Is this class also closed under some operations, like multiplication, exponentiation by a constant, or taking logarithms? And, perhaps, could we even justify why any algorithm is likely to have a complexity in this class?

• Are you consider the smallest class closed with respect to the operations and containing the function $n$ (and, possibly, a constant function) as nice? – Alex Ravsky Aug 12 '17 at 17:15
• Possibly! Is that linearly ordered by my ordering? Can we perhaps even justify that it makes sense as a "class of complexities"? – Mees de Vries Aug 12 '17 at 17:17

• Extremely slow-growing: There are algorithms whose complexity uses inverse Ackermann (union-find) or $\log^{\ast} n$ (distributed tricoloring of a tree). Those functions grow slower than $\log(\log(\dots n\dots))$ for any finite number of logs.
• Extremely fast-growing: Some problems cannot be solved in time that is $\exp(\exp(\dots n \dots))$, for any finite number of $n$. They are called nonelementary. The Ackermann function grows too fast, an according to this answer there are natural problems with Ackermannian complexity.
• Arbitrary: For most sensible functions $F$, it's possible to have an algorithm with complexity $F(n)$, that gets a Turing machine and simulates it for $F(n)$ steps. For example, you can obtain an algorithm with complexity $n^{5+(-1)^n}$. You can also define (artificially) a problem that can be solved in this time.
• Ill-defined: Blum's speedup theorem shows that there exists a computable function $f$ such that, if $f$ can be computed in time $X$, then $f$ can computed in time $\log X$. There is no "best" algorithm to compute $f$. It's not "natural" because it's a diagonalization against possible algorithms, but shows how weird this can get.