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$

2 Answers 2

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$
2
  • $\begingroup$ Thanks. For the log(n) + log(n^2) question, is big-Theta(log(n)) correct? $\endgroup$
    – Smart Home
    Commented May 15, 2016 at 7:33
  • $\begingroup$ @SmartHome Correct, since it is equal to $3 \log(n)$ as you said above. $\endgroup$
    – chi
    Commented May 15, 2016 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$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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