7
$\begingroup$

Why is $\log(n!)=\Theta(n\log n)$?

I tried: $\log(n!) = \log1 + \dots + \log n \leq n \log n \Rightarrow \log(n!) = O(n \log n)$.

But how can we prove $\log(n!) = \Omega(n \log n)$ without Sterling's approximation?

$\endgroup$
0

2 Answers 2

13
$\begingroup$

$$\begin{align*} \log n! &=\sum_{i=1}^n\log i \\ &\geq \sum_{i=\lceil n/2\rceil}^n \log i \\ &\geq \sum_{i=\lceil n/2\rceil}^n \log \tfrac{n}{2} \\ &\geq \tfrac{n}{2}\log \tfrac{n}{2} \\ &= \tfrac{n}{2}\big(\log n - \log 2)\\ &= \Omega(n\log n)\,. \end{align*}$$

$\endgroup$
1
  • $\begingroup$ Can someone explain the steps here? $\endgroup$ Feb 19, 2020 at 15:20
0
$\begingroup$

For all integers $n$, if $n \geq 16$ then

$$ \begin{align*} \log(n!) \; & = \; \log(1)\hspace{.04 in}+\hspace{.04 in}...+\log(n) \\ & \geq 0\hspace{.04 in}+\hspace{.04 in}...+\hspace{.04 in}0+\log(\lfloor n\hspace{.02 in}/\hspace{.02 in}2\rfloor)\hspace{.04 in}+\hspace{.04 in}...+\log(n) \; \\ & = \; 0+\log(\lfloor n\hspace{.02 in}/\hspace{.02 in}2\rfloor)\hspace{.04 in}+\hspace{.04 in}...+\log(n) \\ & = \log(\lfloor n\hspace{.02 in}/\hspace{.02 in}2\rfloor)\hspace{.04 in}+\hspace{.04 in}...+\log(n) \; \\ & \geq \; (1\hspace{-0.05 in}+\hspace{-0.02 in}n\hspace{-0.04 in}-\hspace{-0.05 in}\lfloor n\hspace{.02 in}/\hspace{.02 in}2\rfloor) \cdot \log(\lfloor n\hspace{.02 in}/\hspace{.02 in}2\rfloor) \\ & = (1\hspace{-0.05 in}+\hspace{-0.05 in}\lceil n\hspace{.02 in}/\hspace{.02 in}2\rceil) \cdot \log(\lfloor n\hspace{.02 in}/\hspace{.02 in}2\rfloor) \; \\ & \geq \; (n\hspace{.02 in}/\hspace{.02 in}2) \cdot \log((n\hspace{.02 in}/\hspace{.02 in}2)\hspace{-0.03 in}-\hspace{-0.04 in}(1\hspace{.02 in}/\hspace{.02 in}2)) \\ & = (n\hspace{.02 in}/\hspace{.02 in}2) \cdot \log((n\hspace{.02 in}/\hspace{.02 in}4)\hspace{-0.03 in}+\hspace{-0.03 in}(n\hspace{.02 in}/\hspace{.02 in}4)\hspace{-0.03 in}-\hspace{-0.03 in}(2\hspace{.02 in}/\hspace{.02 in}4)) \; \\ & \geq \; (n\hspace{.02 in}/\hspace{.02 in}2) \cdot \log((n\hspace{.02 in}/\hspace{.02 in}4)\hspace{-0.03 in}+\hspace{-0.03 in}(2\hspace{.02 in}/\hspace{.02 in}4)\hspace{-0.03 in}-\hspace{-0.03 in}(2\hspace{.02 in}/\hspace{.02 in}4)) \\ & = (n\hspace{.02 in}/\hspace{.02 in}2) \cdot \log((n\hspace{.02 in}/\hspace{.02 in}4)\hspace{-0.03 in}+\hspace{-0.03 in}0) \; = \; (n\hspace{.02 in}/\hspace{.02 in}2) \cdot \log(n\hspace{.02 in}/\hspace{.02 in}4) \; \\ & \geq \; (n\hspace{.02 in}/\hspace{.02 in}2) \cdot \log(\sqrt n) \; = \; (n\hspace{.02 in}/\hspace{.02 in}2) \cdot \log\hspace{-0.05 in}\left(\hspace{-0.02 in}n^{1/\hspace{.02 in}2}\hspace{-0.03 in}\right) \\ & = n\cdot (1\hspace{.02 in}/\hspace{.02 in}2) \cdot (1\hspace{.02 in}/\hspace{.02 in}2) \cdot \log(n) \; \\ & = \; n\cdot (1\hspace{.02 in}/\hspace{.02 in}4) \cdot \log(n) \; \\ & = \; (1\hspace{.02 in}/\hspace{.02 in}4) \cdot n \cdot \log(n) \end{align*} $$

$\endgroup$
2
  • 2
    $\begingroup$ you can use Latex's align for better readability $\endgroup$
    – Ran G.
    Oct 17, 2015 at 17:35
  • $\begingroup$ There is no need for such a lengthy development. After the second line, $\ge \frac n2\log\frac n2$, which is $\Theta(n\log n)$. $\endgroup$ Jun 27 at 8:02

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