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?
$\begingroup$
$\endgroup$
5
-
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 ColemanNov 26, 2019 at 0:20
-
3$\begingroup$ Write down the values for 1 ≤ n ≤ 10. You can't? Why can't you? $\endgroup$– gnasher729Nov 26, 2019 at 13:18
-
9$\begingroup$ Why is this in CS instead of Mathematics? $\endgroup$– BarmarNov 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$– OmGNov 27, 2019 at 15:14
-
$\begingroup$ see Stirling's approximation. $\endgroup$– Will NessNov 27, 2019 at 16:36
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
3
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$– chiNov 26, 2019 at 19:07
-
1$\begingroup$ @chi You are right. But, it is true if $\log(f) = o(\log(g))$. $\endgroup$– OmGNov 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$ Nov 28, 2019 at 15:19
$\begingroup$
$\endgroup$
3
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$ 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$ 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$ Nov 27, 2019 at 12:05
$\begingroup$
$\endgroup$
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.
answered Nov 26, 2019 at 13:07
$\begingroup$
$\endgroup$
3
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.
-
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$– ComFreekNov 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$ 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$ Nov 27, 2019 at 23:42