# What is the mistake in my derivation of the wrong asymptotic relation $n^n = O(n!)$?

Since $$n^n = e^{n\log(n)}$$, the Taylor series of $$e^n$$ gives $$n^n = 1+n\log(n)+O(n^2 \log^2(n)).$$

And $$n\log(n) \in O(n!)$$ and $$O(n^2 \log^2(n)) \subset O(n!)$$, so $$n^n = O(n!)$$, which is ridiculous.

Could you please point out any mistakes in my calculation? Thank you in advance. Any comment or answer is appreciated.

• You have written $$n^n = 1+n\log(n)+O(n^2 \log^2(n)).$$ Is the last part really $O(n^2 \log^2n)$? Nov 26, 2021 at 17:48
• Sorry I honestly do not know. What is the mistake here? I subed $n^2\log^2n$ into $e^n = 1+n+O(n^2).$ Nov 26, 2021 at 17:59
• What would be the next term in the Taylor expansion, and is it really smaller than your $O$-term? Note that you are considering $n \to \infty$, not $n \to 0$. Nov 26, 2021 at 18:00
• Oh! It seems that this expansion works only when $n\to 0$? Nov 26, 2021 at 18:03
• Well yes and no, the Taylor series converges everywhere, but if you truncate it, things go awry for large $n$ since you're cutting off higher order terms---those terms are big if $n$ is big, and they're small if $n$ is small. Nov 26, 2021 at 18:06

For $$x$$ large, the terms in the Taylor series $$e^x = 1 + x + \frac{x^2}{2} + \frac{x^3}{3!} + \dots$$ grow larger and larger, so truncating the series will give a wildly wrong estimate (and it will get more wrong the larger $$x$$ gets).