<p>That's a nice list! Unfortunately, I think the function <span class="math-container">$n\left(\log(n)^{\log\log(n)}\right)$</span> is not in your list. Yet it grows faster than <span class="math-container">$n\log(n)$</span> and slower than <span class="math-container">$n^{1+\varepsilon}$</span>. Similarly, the function <span class="math-container">$n\left(\log\log(n)^{\log\log\log(n)}\right)$</span> is not in there, yet it grows faster than <span class="math-container">$n\log\log(n)$</span> but slower than <span class="math-container">$n\log(n)^{\varepsilon}$</span>.</p>

<p>For inspiration, check out comment 52 on <a href="https://www.scottaaronson.com/blog/?p=263" rel="nofollow noreferrer">This blog of Scott Aaronson</a>, where he reflects on half-exponential functions, among other things. He considers a classification not unlike your own, and proves that it does not capture all asymptotic growth rates. I like your idea, and I hope you learn something from that blog post.</p>

CC BY-SA 4.0
2019-05-25T10:49:36.180Z
2019-05-25T10:49:36.180Z
Lieuwe Vinkhuijzen
<p>We all know that exponential functions grow faster than polynomials. Let us consider the following function: <span class="math-container">$f(n)=n^{a_1}⋅(\log n)^{a_2}⋅(\log\log n)^{a_3}⋅(\log\log\log n)^{a_4}⋯ $</span> where the leading coefficient <span class="math-container">$a_k$</span> is positive.</p>

<p>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 <span class="math-container">$n$</span> and <span class="math-container">$n \log n$</span> other than a member of the above class, for instance <span class="math-container">$n⋅(\log n)^{1/2}⋅(\log\log\log n)^5/(\log\log n)^3$</span>.</p>

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

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

<p>(2) Provide an example of function growing faster than the fastest growing function in that class, but more slowly than <span class="math-container">$\exp n$</span>.</p>

<p>(3) What happens if you allow the coefficients <span class="math-container">$\{a_k\}$</span> not to be bounded, and the sequence <span class="math-container">$\{a_k\}$</span> to be infinite? For instance consider <span class="math-container">$f(n)=n⋅(\log n)^2⋅(\log\log n)^4⋅(\log\log\log n)^8⋯$</span>.</p>

<p>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.</p>

CC BY-SA 4.0
2019-05-25T01:29:00.287Z
I highly doubt your representation is "complete" unless you want to restrict yourself to (elementary functions)[https://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
CC BY-SA 4.0
2019-05-25T02:51:34.177Z
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
CC BY-SA 4.0
2019-05-25T03:01:00.203Z
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
CC BY-SA 4.0
2019-05-25T04:13:24.403Z
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
CC BY-SA 4.0
2019-05-25T04:14:01.773Z
Oh, also, in between $n$ and $n\log n$: $nA^{-1}(n)$, where $A$ is the Ackermann function.
Joshua Grochow
CC BY-SA 4.0
2019-05-25T04:39:10.943Z
Your two last comments actually answer my question. I'll check those functions, hopefully it will become clear to me why they don't belong to my family, resulting in my family not being "complete". I'm still interested to find a "complete" family with as few elements as possible (though of course the number of elements will be infinite, maybe countably infinite.)
Vincent Granville
<cc.complexity-theory><asymptotics>
Comprehensive list of functions used in Big-$O$ notation
Vincent Granville
# Comprehensive list of functions used in Big-$O$ notation

(Asked by: username_0 on 2019-05-24)

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.

**Tags:** cc.complexity-theory, asymptotics

> **Comments:**
> **username_1**: I highly doubt your representation is "complete" unless you want to restrict yourself to (elementary functions)[https://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..  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_1**: 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...)  
> **username_1**: Oh, also, in between $n$ and $n\log n$: $nA^{-1}(n)$, where $A$ is the Ackermann function.  
> **username_0**: Your two last comments actually answer my question. I'll check those functions, hopefully it will become clear to me why they don't belong to my family, resulting in my family not being "complete". I'm still interested to find a "complete" family with as few elements as possible (though of course the number of elements will be infinite, maybe countably infinite.)  

---

## 1 answers

### Answer by username_2 on 2019-05-25. Score: 1 | Accepted answer

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}$.

For inspiration, check out comment 52 on [This blog of Scott Aaronson](https://www.scottaaronson.com/blog/?p=263), where he reflects on half-exponential functions, among other things. He considers a classification not unlike your own, and proves that it does not capture all asymptotic growth rates. I like your idea, and I hope you learn something from that blog post.


---

