patternMajor
Which Grows Faster: Factorial or Double Exponentiation
Viewed 0 times
factorialgrowsfasterdoublewhichexponentiation
Problem
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?
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?
Solution
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!$.
$$\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!$.
Context
StackExchange Computer Science Q#117577, answer score: 46
Revisions (0)
No revisions yet.