patternMinor
Is $\log(n!)$ in $\Theta(n \log(n))$?
Viewed 0 times
thetalogstackoverflow
Problem
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?
$\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?
Solution
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))$.
$$
\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))$.
Context
StackExchange Computer Science Q#57457, answer score: 7
Revisions (0)
No revisions yet.