Is log n! = Θ(n log n)? [duplicate]

Question

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?

Answer 1

$$\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*}$$

Answer 2

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

$\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)$

.