636 views
asked | 636 views

I think it is sterling's approximation

$$\ln N! = N \ln N - N + \ln \sqrt{2 \pi n}$$
answered by (215 points)
selected by
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)$.
answered by (31 points)
+2
It is true for big O. But for $\Theta$ notation can we say $n! = \Theta (n^n)$?
0
no such constant exists for n^n, whereas for the nlogn I think it is 1/2