# how to prove that log(n!) >= c n log(n) for some c >0?

as reading the book Algorithms by Dasgupta, C.H Papadimitriou. on Page 63.

And it is well known that $$\log(n!)≥c\cdot n\cdot\log n$$ for some $$c > 0$$. There are many ways to see this. The easiest is to notice that $$n! \ge (n/2)^{(n/2)}$$ because $$n! = 1 · 2\cdot\cdots\cdot n$$ contains at least $$n/2$$ factors larger than $$n/2$$; and to then take logs of both sides. Another is to recall Stirling’s formula.

Can someone help to find the proof on $$n! \ge (n/2)^{(n/2)}$$, or how should we prove it ourselves? As we take log on both side, it became (assuming that its base is some number constant) $$\log(n!)$$ on the left side, on the right, it became $$\log\left((n/2)^{(n/2)}\right)$$, further simplify $$(n/2)\log(n/2)$$ --> $$(n/2)\log(n^{-2})$$, then finally on the right side: $$(-n)\log(n)$$. Then we completed the proof (?)

I have two questions, is the proof of $$n! \ge (n/2)^{(n/2)}$$ corrected? If so, how can we argue back to "$$\log(n!)≥c\cdot n\cdot\log n$$ for some $$c > 0$$", if not, how can we proof that "$$\log(n!)≥c\cdot n\cdot\log n$$ for some $$c > 0$$"?

• n! is the product of the numbers 1 to n. The last n/2 of those are all > n/2. Aug 13, 2019 at 7:50

... further simplify $$(n/2)\log(n/2)$$ --> $$(n/2)\log(n^{-2})$$, ...
This is wrong. In fact, for $$n\ge 3$$, $$n^{\log_3 2}\ge 2$$, so \begin{align} (n/2)\log(n/2)&=(n/2)(\log n-\log2)\\ &\ge (n/2)\cdot\left(1-\log_3 2\right)\log n\\ &=\left(1-\log_3 2\right)/2\cdot n\cdot \log n, \end{align} and $$\log(n!)\ge \left(1-\log_3 2\right)/2\cdot n\cdot \log n$$ also holds for $$n=1,2$$, which completes the proof.
$$n! = n \cdot (n-1) \cdot ... \cdot 1 \ge n \cdot (n-1) \cdot ... \cdot (n/2) \ge (n/2)^{(n/2)}$$
$$\log(n!)≥c\cdot n\cdot\log n$$ for $$c \ge 1/2$$