# Which Grows Faster: Factorial or Double Exponentiation

Which of the functions among $$2^{3^n}$$ or $$n!$$ grows faster?

I know that $$n^n$$ grows faster than $$n!$$ and $$n!$$ grows faster than $$c^n$$ where $$c$$ is a constant, but what is it in my case?

• It isn't a proof, but evaluate the expressions with $n$ in the range 1 to 10 and see just how phenomenally fast $2^{3^n}$ grows compared to $n!$ – John Coleman Nov 26 '19 at 0:20
• Write down the values for 1 ≤ n ≤ 10. You can't? Why can't you? – gnasher729 Nov 26 '19 at 13:18
• Why is this in CS instead of Mathematics? – Barmar Nov 26 '19 at 21:08
• @Barmar because it's related to CS in terms of time complexity. Indeed, in this question, there is not a hard border between math and CS. – OmG Nov 27 '19 at 15:14
• – Will Ness Nov 27 '19 at 16:36

You can find the result by taking a $$\log$$. Hence:

$$\log(2^{3^n}) = 3^n$$ $$\log(n!) \leqslant \log(n^n) = n\log n$$

(In the latter equation, we have used the fact that $$n! \leqslant n^n$$, as you note in the question.)

Of course $$3^n$$ grows faster than $$n \log n$$. As $$\log$$ is an increasing function, we can say $$2^{3^{n}}$$ grows faster than $$n^n$$, and also $$n!$$.

• Beware, however, that $\log(f) = O(\log(g))$ does not imply $f = O(g)$, in general. For instance, take $f(n)=n^2$ and $g(n)=n$. – chi Nov 26 '19 at 19:07
• @chi You are right. But, it is true if $\log(f) = o(\log(g))$. – OmG Nov 26 '19 at 19:56
• Another question related with taking log and solving and its danger is given in this link--> cs.stackexchange.com/questions/117584/… – Turing101 Nov 28 '19 at 15:19

Another way to directly compare the two expressions is to take the ratio of consecutive terms:

$$\frac{2^{3^{n+1}}}{2^{3^n}}=2^{2\cdot 3^n}\gg 3^n\gg n+1=\frac{(n+1)!}{n!}$$

(for positive integers $$n$$), and clearly also $$2^{3^1}=8>1!$$, so $$2^{3^n}$$ indeed grows more rapidly than $$n!$$.

• The discussion of $2^{3^1}$ is unnecessary. – leftaroundabout Nov 27 '19 at 1:56
• @leftaroundabout, I guess that's true if you assume the >> signs are significantly greater than, but that's not very rigorous (and if they are only > signs it would then depend on your definition of "grows more rapidly") – boboquack Nov 27 '19 at 7:43
• Well, they only need to be “significantly” greater in a very weak sense, namely the ratio needs to be $>1+\varepsilon$. That is clearly given in this case, specifically $\frac{3^n}{n+1} > 1.5\quad \forall n>0$. – leftaroundabout Nov 27 '19 at 12:05

You noted in your question that $$n^n$$ grows faster than $$n!$$, and that’s a great starting point for comparing the growth of $$2^{3^n}$$ and $$n!$$. Specifically, let’s ask - of $$n^n$$ and $$2^{3^n}$$, which grows faster?

To answer that, let’s try rewriting $$n^n$$ so that it has the same exponential base as $$2^{3^n}$$. Since $$n = 2^{\log_2 n}$$, we have that

$$n^n = (2^{\log_2 n})^n = 2^{n \log_2 n}.$$

Now, is it easier to see how $$n^n$$ and $$2^{3^n}$$ relate?

As a note, this approach is similar to taking the base-2 logs of both expressions. I thought it would be good to include this here because it gives a slightly different perspective on how to arrive at the answer given your initial observation.

Induction.

Base case: $$n=1$$ gives $$2^{3^1}=8$$ and $$1!=1$$ which clearly holds.

Hypothesis: suppose that $$2^{3^k}>k!$$ for some $$k\in\Bbb N$$.

Consider $$n=k+1$$. Then $$2^{3^{k+1}}=2^{3^k\cdot3}>(k!)^3=(k+1)!\cdot\frac{k!(k-1)!}{1+\frac1k}>(k+1)!$$ which is true $$\forall k>1$$ and thus the result follows.

• I tend to interpret "which grows faster?" questions as "whose big-Oh set is bigger?". With that interpretation, this post answers something different. (E.g. $x \mapsto x$ and $x \mapsto (x+1)$ are in the same big-Oh set, but in the spirit of this post the latter grows faster.) – ComFreek Nov 26 '19 at 12:02
• @ComFreek I would really have to question that interpretation. Which grows faster, $f(x) = x$ or $g(x) = 2x$? I think by any reasonable meaning of the words "grow" and "faster", $2x$ grows faster than $x$. My definition of grows faster would be $f(x)$ grows faster than $g(x)$ if there exists an $x_0$ beyond which $f'(x)$ is always greater than $g'(x)$. – Apollys supports Monica Nov 27 '19 at 23:36
• That being said, this proof certainly doesn't prove anything about growth rates. Plug in the functions $f(x) = -1/x$ and $g(x) = 0$ (on the domain $x > 0$) into your proof and you conclude that $g(x)$ grows faster than $f(x)$. This is obviously wrong since $g(x)$ never grows and $f(x)$ never doesn't grow! – Apollys supports Monica Nov 27 '19 at 23:42