Problem Detail: I had two questions on my automated test which I don’t understand the answer for. $log(n!) = log(ncdot (n-1)cdot cdots cdot 2cdot 1) = log(n)+log(n-1)+….+log(1)$. So it is in $O(nlog(n))$. But is it also in $Omega(n log(n))$? I don’t think so, but my automated interview test thought so! $log(n)+log(n^2) = log(n)+2log(n) = 3log(n)$. So, it is in $O(log(n))$, $Omega(log(n))$ and $Theta(log(n))$. But for some reason my automated interview test thought otherwise. Is my understanding correct or is the automated test correct?
Asked By : Smart Home
Answered By : chi
You mentioned $$ log(n!) = log(n(n-1)cdots1) = log(n)+log(n-1)+ cdots +log(1) $$ From this, we can write (assuming $log$ is base 2) $$ begin{array}{l} log(n!) = log(n)+log(n-1)+….+log(1) geq log(n)+ cdots + log(n/2) geq log(n/2)+ cdots + log(n/2) = n/2 cdot log(n/2) = n/2 cdot (log(n) – 1) = n/2 cdot log(n) – n/2 end{array} $$ since $lim_{nrightarrow +infty} dfrac{n/2}{n/2 cdot log(n)} = 0$, the last expression above is $Theta(n log(n))$, hence $log(n!)$ is $Omega(n log(n))$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/57457
