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?

  • 2
    $\begingroup$ 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!$ $\endgroup$ Commented Nov 26, 2019 at 0:20
  • 3
    $\begingroup$ Write down the values for 1 ≤ n ≤ 10. You can't? Why can't you? $\endgroup$
    – gnasher729
    Commented Nov 26, 2019 at 13:18
  • 9
    $\begingroup$ Why is this in CS instead of Mathematics? $\endgroup$
    – Barmar
    Commented Nov 26, 2019 at 21:08
  • 3
    $\begingroup$ @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. $\endgroup$
    – OmG
    Commented Nov 27, 2019 at 15:14
  • $\begingroup$ see Stirling's approximation. $\endgroup$
    – Will Ness
    Commented Nov 27, 2019 at 16:36

4 Answers 4


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

  • 6
    $\begingroup$ 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$. $\endgroup$
    – chi
    Commented Nov 26, 2019 at 19:07
  • 1
    $\begingroup$ @chi You are right. But, it is true if $\log(f) = o(\log(g))$. $\endgroup$
    – OmG
    Commented Nov 26, 2019 at 19:56
  • $\begingroup$ Another question related with taking log and solving and its danger is given in this link--> cs.stackexchange.com/questions/117584/… $\endgroup$
    – Turing101
    Commented Nov 28, 2019 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!$.

  • 1
    $\begingroup$ The discussion of $2^{3^1}$ is unnecessary. $\endgroup$ Commented Nov 27, 2019 at 1:56
  • $\begingroup$ @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") $\endgroup$
    – boboquack
    Commented Nov 27, 2019 at 7:43
  • $\begingroup$ 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$. $\endgroup$ Commented Nov 27, 2019 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.



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.

  • 1
    $\begingroup$ 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.) $\endgroup$
    – ComFreek
    Commented Nov 26, 2019 at 12:02
  • $\begingroup$ @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)$. $\endgroup$ Commented Nov 27, 2019 at 23:36
  • $\begingroup$ 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! $\endgroup$ Commented Nov 27, 2019 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.