Rate of growth of exponential and factorial

Question

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.

Answer 1

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.

Answer 2

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