I am trying to determine which function grows faster: $g(n) = n^{({\ln n})^n}$ or $f(n)=(n!)^{2^{n}}$.

Based on intuition, my idea was to compare either bases or powers and hopefully to find which function grows faster, but that's not the case here.

My first attempt was to find $\lim{\frac{g(n)}{f(n)}}$ while $n \rightarrow \inf$, but that doesn't seem feasible with powers of powers.

Also I tried to substitute $n!$ with Striling's approximation, but I don't know what to do next, because it doesn't make the comparison any simplier.

I was trying to find any similar questions on MSE (in fact, there are quite a few), but none of them are about such complex functions.

Looking forward to any ideas that may help me.

  • $\begingroup$ Rather than replacing $n!$ with stirlings approximation, replacing $\ln(n!)$ with stirlings approximation is going to be cleaner. $\endgroup$ – JMoravitz Oct 9 at 19:24

We have that

  • $g(n) = n^{({\ln n})^n}=e^{({\ln n})^{n+1}}$

  • $f(n)=(n!)^{2^{n}}=e^{2^{n}\log n!}$

and by ratio test

$$\frac{{({\ln (n+1)})^{n+2}}}{{2^{n+1}\log (n+1)!}}\frac{{2^{n}\log n!}}{{({\ln n})^{n+1}}}=\frac{\log(n+1)}2\left(1+\log(1+1/n)\right)^{n+1}\frac1{1+\frac{\log(n+1)}{\log n!}}\to \infty$$

therefore $g(n)$ grows faster.


Take ln n = k

$g(n) = n^{(k)^n}$ or $f(n)=(n!)^{2^{n}}$ $g(n)=e^{k^n\ln n}$ and $f(n)=e^{2^n\ln n}*(n-1)!$

Now you can see ln n increases very slowly whereas 2 doesn't increase but (n-1)! Increases so fast.

And difference between 2 and ln n is significant when n is very high but at that n (n-1)! Is much much larger.

So f(n) grows faster


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.