Question

Is the following statement valid? $$\log(n!) = \Theta(n \log n)$$

Answer 1

I think it is sterling's approximation

$$\ln N! = N \ln N - N + \ln \sqrt{2 \pi n} $$

Answer 2

n! corresponds to n*(n-1)*(n-2)*....*1 which is $\Theta (n^n)$. So by taking $\log$ to both terms, the answer comes out to be $\Theta(n \log n)$.

Comments

It is true for big O. But for $\Theta$ notation can we say $n! = \Theta (n^n)$?

---

no such constant exists for n^n, whereas for the nlogn I think it is 1/2