Can we write $n!$ as $n^n$

Question

I came to see the complexity analysis of an algorithm where it is written $O(\log n!) \sim O(\log n^n) \sim O(n \log n)$. My question is how could $n!$ be equivalent to $n^n$ or the article made some wrong assumption?

Answer 1

For large values of $n$, https://en.wikipedia.org/wiki/Stirling%27s_approximation this is known as stirling's approximation $$\ln{n!} = n\ln n -n + O(\ln n) $$ Hence, $$ O(\ln{n!}) \approx O(n\ln n) $$ $$ = O(ln n^n)$$

Answer 2

Write $\log n!=\sum_{k=1}^n\log k$ ; this sum can be approximated by the integral $\int_{1}^{n}\log x dx$ which is $\Theta(n\log n)$.

Answer 3

Here's an approach just using some simple algebra to compare $\log n!$ and $\log n^n$:

If $0\le k\le n-1$, then $n\le n+k(n-k-1)=(n-k)(k+1)$. It follows that

$$n^n\le(n\cdot1)((n-1)\cdot2)\cdots(2\cdot(n-1)(1\cdot n)=(n!)^2$$

and thus $n\log n\le 2\log n!$. Since

$$\log n!=\log n+\log(n-1)+\cdots+\log2+\log1\le\log n+\log n+\cdots+\log n+\log n=n\log n$$

is clear, we have

$${1\over2}n\log n\le\log n!\le n\log n$$

hence $O(\log n!)\sim O(\log n^n)=O(n\log n)$.