Which grows faster $n!$ or $n^{\sqrt{n}}$?

320 Views Asked by At

From graph it can be easily seen that $n!$ grows faster that $n^{\sqrt{n}}$. Also wolfram alpha says that $\lim _{n\to \infty }\left(\frac{n^{\sqrt{n}}}{n!}\right)=0$. I'd appreciate if anyone could explain how, being a complete noob I don't know how to compute the limit of the above function.

I also tried taking log of both the functions and then solving it through PMI, but no luck.

2

There are 2 best solutions below

3
On

Taking logarithm makes things simpler:

$$ \log n!=\sum_{1\le k\le n}\log k>\sum_{1\le k\le n}\int_{k-1}^k\log t\mathrm dt=\int_0^n\log t\mathrm dt=n\log n-n $$

Since $n\log n$ grows significantly faster than $n$ and $\sqrt n\log n$, we conclude $n!$ grows much faster than $n^{\sqrt n\log n}$, making that limit zero.

3
On

A very easy way to see that these kind of limits are true is to use Stirling's Approximation which says $$n!\sim \sqrt{2\pi n}\left(\frac ne\right)^n$$ So, $$\left(\frac{n^{\sqrt{n}}}{n!}\right)\sim\left(\frac{n^{\sqrt{n}}}{\sqrt{2\pi n}\left(\frac ne\right)^n}\right)=n^{\sqrt n-n-\frac 12}e^n(2\pi)^{-1}=(2\pi)^{-1}\frac{e^n}{n^{n-\sqrt n+\frac 12}}$$ which is approximately $\frac{e^n}{n^n}$ for large $n$.

So, the limit is $0$.


As mark Viola pointed out, an easier way is to use $n!\ge \left(\frac n2\right)^{n/2}$. This can be derived easily from the fact that $\left(n!\right)^2\ge n^n$.