26
$\begingroup$

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?

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

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

$\endgroup$
  • 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 Nov 26 '19 at 19:07
  • 1
    $\begingroup$ @chi You are right. But, it is true if $\log(f) = o(\log(g))$. $\endgroup$ – OmG Nov 26 '19 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 Nov 28 '19 at 15:19
26
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ The discussion of $2^{3^1}$ is unnecessary. $\endgroup$ – leftaroundabout Nov 27 '19 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 Nov 27 '19 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$ – leftaroundabout Nov 27 '19 at 12:05
10
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 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 Nov 26 '19 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$ – Apollys supports Monica Nov 27 '19 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$ – Apollys supports Monica Nov 27 '19 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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