1
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ 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)$? $\endgroup$
    – Aryaman Maithani
    Nov 26, 2021 at 17:48
  • $\begingroup$ 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).$ $\endgroup$
    – user628623
    Nov 26, 2021 at 17:59
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Jakob Streipel
    Nov 26, 2021 at 18:00
  • $\begingroup$ Oh! It seems that this expansion works only when $n\to 0$? $\endgroup$
    – user628623
    Nov 26, 2021 at 18:03
  • $\begingroup$ 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. $\endgroup$
    – Jakob Streipel
    Nov 26, 2021 at 18:06

1 Answer 1

Reset to default
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .