I have a problem where I have to compare two functions and tell which one grows faster:
$$f(n) = n!, \quad g(n) = n^{\log_2n}.$$
However, I do not know how to tell which one is greater or reduce them with the limit definition. If I decompose both function I get $$n! = n(n-1)(n-2)\cdots1$$ and $$n^{\log_2n} = \underbrace{n·n·n\cdots}_{\log_2n \text{ times}}.$$
My intuition tells me $n!$ is bigger, because the $\log_2n$ grows very slowly so the accumulated product of $n$ must grow slower than $n!$.
Thank you.
By Stirling's formula, we see that \begin{align} n! \sim \sqrt{2\pi n}\left( \frac{n}{e}\right)^n \end{align} Then it follows \begin{align} \frac{n!}{n^{\log_2 n}} \sim \sqrt{2\pi n}\frac{n^{n-\log_2 n}}{e^n} = \sqrt{2\pi n} e^{(n-\log_2 n)\log_e n-n}\gg \sqrt{n} \end{align} for $n\gg 1$.