# Comprehensive list of functions used in Big-$O$ notation

We all know that exponential functions grow faster than polynomials. Let us consider the following function: $$f(n)=n^{a_1}⋅(\log n)^{a_2}⋅(\log\log n)^{a_3}⋅(\log\log\log n)^{a_4}⋯$$ where the leading coefficient $$a_k$$ is positive.

I think anything that is "slowly growing" has this type of asymptotic expansion. In short, this type of representation is "complete": there is nothing between $$n$$ and $$n \log n$$ other than a member of the above class, for instance $$n⋅(\log n)^{1/2}⋅(\log\log\log n)^5/(\log\log n)^3$$.

Is my statement true? How can one make it rigorous, assuming it is correct? Also,

(1) What would be the slowest growing function that grows faster than the fastest growing function in the above class?

(2) Provide an example of function growing faster than the fastest growing function in that class, but more slowly than $$\exp n$$.

(3) What happens if you allow the coefficients $$\{a_k\}$$ not to be bounded, and the sequence $$\{a_k\}$$ to be infinite? For instance consider $$f(n)=n⋅(\log n)^2⋅(\log\log n)^4⋅(\log\log\log n)^8⋯$$.

In short, is there some kind of topological framework that handles manipulations over these functions? Indeed, they are not functions, but asymptotic representations or quantities instead. It's a different type of mathematical objects, with its own arithmetic and topology.

• I highly doubt your representation is "complete" unless you want to restrict yourself to (elementary functions)[en.wikipedia.org/wiki/Elementary_function] (and then it's almost complete by definition). You can consider functions defined by an algorithm but with no simple closed-form expression. (1) There's probably no single slowest such function; since it's asymptotic, I think you can always sandwich something in between as you go out to far enough $n$. (2) $n^{\log n}$. (3) Never converges; $\forall n$, if you take $\log$ enough times you get a negative number, then one more.. – Joshua Grochow May 25 '19 at 1:29
• To clarify, I consider $n^2/(n+1)$ and $n+\log n$ to be the same, that is, being asymptotically equivalent. But I don't want to restrict myself to elementary functions. – Vincent Granville May 25 '19 at 2:51
• Regarding (3) yes there is an issue. Maybe $\log|\log|\log|\cdots |||$ could work instead (using the absolute value of the log function, rather than the log function.) But this opens up a new can of worms: the sequence $x(n+1) = |\log x(n)|$ with $x(1) = 2$ is well defined for instance, but it's not getting smaller as $n$ increases. It seems to be ergodic, actually, and very well behaved from a probabilistic point of view. – Vincent Granville May 25 '19 at 3:01
• Even under asymptotic equivalence (and do you want $\lim f/g = 1$ or big-Theta or something else?), I think there are probably more equivalence classes than closed-form formulas. For example, half-exponential functions ($f$ such that $f(f(n))=2^n$) or the Lambert W function. Maybe a cardinality argument would work? (e.g. say we use big-Theta consider only formulas with integer coefficients...) – Joshua Grochow May 25 '19 at 4:13
• Oh, also, in between $n$ and $n\log n$: $nA^{-1}(n)$, where $A$ is the Ackermann function. – Joshua Grochow May 25 '19 at 4:14

That's a nice list! Unfortunately, I think the function $$n\left(\log(n)^{\log\log(n)}\right)$$ is not in your list. Yet it grows faster than $$n\log(n)$$ and slower than $$n^{1+\varepsilon}$$. Similarly, the function $$n\left(\log\log(n)^{\log\log\log(n)}\right)$$ is not in there, yet it grows faster than $$n\log\log(n)$$ but slower than $$n\log(n)^{\varepsilon}$$.