3
$\begingroup$

I had two questions on my automated test which I don't understand the answer for.

$\log(n!) = \log(n\cdot (n-1)\cdot \cdots \cdot 2\cdot 1) = \log(n)+\log(n-1)+....+\log(1)$. So it is in $O(n\log(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)+2\log(n) = 3\log(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?

$\endgroup$
7
$\begingroup$

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_{n\rightarrow +\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))$.

$\endgroup$
  • $\begingroup$ Thanks. For the log(n) + log(n^2) question, is big-Theta(log(n)) correct? $\endgroup$ – Smart Home May 15 '16 at 7:33
  • $\begingroup$ @SmartHome Correct, since it is equal to $3 \log(n)$ as you said above. $\endgroup$ – chi May 15 '16 at 11:40
6
$\begingroup$

Yes. This follows from Stirling's approximation: $\sqrt{2\pi}\,n^{n+1/2}\,e^{-n}\leq n!\leq e\,n^{n+1/2}\,e^{-n}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.