What is $f(n) = (n+1)!$ which is also $f(n) = (n+1)n!$ in terms of big-O notation? My guess is $O(n \cdot n!)$ but I am not sure. I only know it is certainly $f(n) \in O(n^n)$.
Asked
Active
Viewed 130 times
1 Answers
2
Using Stirling expansion for $n! \sim \sqrt{2 \pi}(\frac{n}{e})^{n} n^{\frac{1}{2}}$ your expression is $n!n +O(n!)$. Hence $(n+1)! \sim \sqrt{2 \pi} n^{n+\frac{3}{2}} e^{-n} +O(n!)$
Alex
- 19,262
-
You're missing the $\sqrt{2\pi}$ from Stirling's formula. – Antonio Vargas Apr 06 '14 at 18:34
-
That's why I used the $\sim$, not the $=$ sign – Alex Apr 06 '14 at 18:44
-
But $\sim$ does not ignore constants. Saying "$n! \sim (n/e)^n \sqrt{n}$" is saying that $$\lim_{n \to \infty} \frac{n!}{(n/e)^n \sqrt{n}} = 1,$$ which isn't true. It is true however that $$\lim_{n \to \infty} \frac{n!}{(n/e)^n \sqrt{2\pi n}} = 1,$$ so $n! \sim (n/e)^n \sqrt{2\pi n}$. – Antonio Vargas Apr 06 '14 at 18:54