0
$\begingroup$

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$"?

$\endgroup$
  • 1
    $\begingroup$ n! is the product of the numbers 1 to n. The last n/2 of those are all > n/2. $\endgroup$ – gnasher729 Aug 13 at 7:50
2
$\begingroup$

... 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.

$\endgroup$
3
$\begingroup$

$n! = n \cdot (n-1) \cdot ... \cdot 1 \ge n \cdot (n-1) \cdot ... \cdot (n/2) \ge (n/2)^{(n/2)}$

so

$\log(n!)≥c\cdot n\cdot\log n$ for $c \ge 1/2$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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