0

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.

Ѕᴀᴀᴅ
  • 34,263
Louis-Vincent Boudreault
  • 13
  • Just one remark : the definition of $n^{\mathrm{log}_2 n}$ is not the one you gave, because "$\mathrm{log}_2 n$ times" has no sense (it's not an integer). The good definition is the exponential definition $a^b = e^{b \ln a}$. – TheSilverDoe Sep 26 '18 at 10:27

1 Answers1

3

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$.

Jacky Chong
  • 25,739