7
$\begingroup$

My homework was proving this equation which is simple using Stirling approximation. I was wondering if there is any other method to prove it - without Stirling - I can prove $\ln(n!) = O(n\ln(n))$ like this: $$\ln(n!)=\ln(n\cdot(n-1)\cdots2\cdot1)=\ln(n)+\ln(n-1)+\cdots+\ln(2)+\ln(1)≤n\ln(n)$$ which is obvious.

But I can't prove that $\ln(n!) = \Omega(n\ln(n))$.

$\endgroup$
7
  • 9
    $\begingroup$ $\log n! \geqslant \sum_{k=n/2}^n \log k \geqslant n/2\log(n/2)$. $\endgroup$
    – Daniel Fischer
    Commented Oct 10, 2013 at 13:26
  • $\begingroup$ thanks. but does log(n!) >= n/2log(n/2) mean Omega(nlogn)? I'm very new to these subjects... $\endgroup$
    – Sida
    Commented Oct 10, 2013 at 13:33
  • 1
    $\begingroup$ For $n \geqslant 4$, you have $n/2 \geqslant \sqrt{n}$, so $\log (n/2) \geqslant \frac12 \log n$, thus for $n\geqslant 4$, you have $\log (n!) \geqslant \frac14 n\log n$. $\endgroup$
    – Daniel Fischer
    Commented Oct 10, 2013 at 13:36
  • $\begingroup$ The one you mentioned @ThomasAndrews, means log(n!) = O(nlogn); not log(n!) = Omega(nlogn), am I right? $\endgroup$
    – Sida
    Commented Oct 10, 2013 at 13:44
  • $\begingroup$ See math.stackexchange.com/questions/46892/…. $\endgroup$
    – lhf
    Commented Oct 10, 2013 at 13:48

1 Answer 1

Reset to default
9
$\begingroup$

Use a multiplicative variant of Gauss's trick: $$ (n!)^2 = (1 \cdot n) (2 \cdot (n-1)) (3 \cdot (n-2)) \cdots ((n-2) \cdot 3) ((n-1) \cdot 2) (n \cdot 1) \ge n^n $$ This implies that $\ln(n!) \ge \dfrac12 n \ln n$.

The other direction is easy, as you mention, because $n! \le n^n$ and so $\ln(n!) \le n \ln n$.

So $\dfrac12 n \ln n \le \ln(n!) \le n \ln n$ and $\ln(n!) = \Theta(n\ln(n))$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .