Exponential and factorial that grow at exactly the same rate

Question

I want to find a relation of the form

$$ n^{n^a} = \Theta (n!) $$

I know and can reason fairly easily that $n^n$, where $a=1$, grows faster than $n!$, and $n^{\sqrt{n}}$, where $a=\frac{1}{2}$, grows more slowly than $n!$, so we can state the bound: $$\frac{1}{2} < a < 1$$ However, there appears to be no value in the bound, even in the limit as $a$ approaches $1$, that can make the exponential grow at exactly the same rate as the factorial. Is there no way to satisfy the above expression (in which case, why?), or have I missed something fairly obvious?

Answer 1

Finally I found some time to expand my comments into a complete answer. I hope this can give you further intuition.

---

Factorials and powers

A well-known approximation of $n!$ is given by Stirling's formula:

$$n!\sim \sqrt{2\pi n}\left(\frac ne\right)^n.$$

We can write the right side as

$$\sqrt{2\pi}\cdot \underbrace{n^{n+1/2-n\log_n(e)}}_{:=\,g(n)}$$

This means, that the best approximation of $n!$ of the form $n^{f(n)}$ is $g\in\Theta(n!)$. More precisely $n!/g(n)\to\sqrt{2\pi}$. Since $f(n)=n+1/2-n\log_n(e)$ is not of the form $n^a$, there is no best value $a$ for this approximation desprite maybe $a=1$ since $f\in\Theta(n^1)$.

Always keep in mind that the Landau notation $\Theta$ (and the related big- and small-O's) are just one way to classify function growth (a very useful one in reality though).

---

Function growth and hyperreals

You understandably wonder about how it can be that just going from $n^1$ to any $n^a,a>1$ suddenly changes the relation between $n!$ and $n^{n^a}$. Shouldn't there be some value $a$ which we can approximate, e.g. with binary search $-$ always checking whether $n^{n^a}$ is finally bigger or smaller than $n!$ and then adjust $a$ a bit?

Qiaochu gave another example: the function $n\log (n)$ is not in any $\Theta(n^a)$ for any $a\in\Bbb R$. So you can find this effect for simpler functions too.

Here is a reasoning on some other basis. Think of the powers $n^a$ as too coarsaly distributed in the set of all functions. I mean that from the point of view of all functions, there are huge gaps between $n^1$ and $n^a$ for any $a>1$. And these gaps are filled with other functions, e.g. $n\log(n)$. Here are some analogies which try to mimic this effect with numbers:

• The set of integers is "coarse" in $\Bbb R$. When you try to approximate $1/2$ using whole numbers, you try $...,-2,-1,0<1/2$ and then "suddenly" the next plausible value $1$ is already above $1/2$.
• The above example might be not so really satisfying since $\Bbb Z$ is too discrete in some sense compared to $\Bbb R$. Try it with $\Bbb Q$ and approximating $\sqrt 2\in\Bbb R$. Any rational number is either below or above $\sqrt 2$.
• This example might still be unsatisfying since there is no "next" value $q\in\Bbb Q$ which suddenly is above $\sqrt 2$. It is more that we never reach $\sqrt 2$ in the first place. Also, the powers $n^a$ are parametrized by a real value $\Bbb R$ and we can hardly imagine that the reals are "too coarse" for parametrizing something. Let me introduce the hyperreal numbers $\Bbb R^*$. They are essentially the reals $\Bbb R$ enriched by infinite numbers (say $\omega$) and infinitesimal (i.e. infinitely small) numbers (say $\epsilon$). We are interested in the infinitesimal number $\epsilon$ which is bigger than $0$ but smaller than any real number $a>0$, i.e. $$0<\epsilon<a,\quad\forall a\in\Bbb R,a>0.$$ Now try to approximate $\epsilon$ with real numbers. Any $a>0$ is too big. No matter how close we approach zero with $a$, we are still above. But then suddenly as we jump to zero, we are below $\epsilon$. So this resembles this exact effect we observed for functions. The reals $\Bbb R$ are "too coarsely distributed" inside the hyperreals $\Bbb R^*$. There is a huge gap between $0$ and any real number $a>0$ which is filled by infinitesimals like $\epsilon,\epsilon^2$ or $\epsilon/2$. You can think of the function $n^{n^a}$ as the hyperreal number $a\in\Bbb R^*$ and $n!$ as the hyperreal number $1+\epsilon$. By the way, usually the hyperreal numbers are exactly constructed by observing this exact phenomenon that you found here. So they are somehow made to resemble this effect.