6
$\begingroup$

This question already has an answer here:

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$

marked as duplicate by D.W. Oct 18 '15 at 0:14

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

11
$\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$
0
$\begingroup$

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

.

$\endgroup$
  • 7
    $\begingroup$ This is completely illegible. $\endgroup$ – David Richerby Oct 17 '15 at 16:11
  • 2
    $\begingroup$ you can use Latex's align for better readability $\endgroup$ – Ran G. Oct 17 '15 at 17:35

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