4
$\begingroup$

In other words, how to prove this equation

$\lg{n!} = \Theta(n\lg{n})$

  • 2
    $\Theta = \mathcal{O} + \Omega$. $\mathcal{O}$ is upper bound, $\Omega$ is lower bound and $\Theta$ is tight bound (both upper and lower). For eg, $n\log n = \mathcal{O}(n^2)$ but not $\Theta(n^2)$, $n \log n = \Omega(n)$ but not $\Theta(n)$ and $n \log n = \Theta(n \log n)$2011-08-05

4 Answers 4

1

Looking at the graph of $\log$ one immediately verifies the inequalities $\int_1^n\log x\ dx <\sum_{k=1}^n\log k<\int_2^{n+1}\log x\ dx\ .$ Evaluating the integrals one gets $n\log n -n+1< \log(n!)<(n+1)\log(n+1)-n + c$ with $c=1-\log 4$, and this easily implies ${\log(n!)\over n\log n}\to 1$ $(n\to\infty)$.

  • 0
    @Pierre-Yves Gaillard: Yes, see here for the definition of various symbols concerning asymptotic behavior: http://en.wikipedia.org/wiki/Big_O_notation2011-08-05
3

Hint: $ n\log \bigg(\frac{n}{e}\bigg) + 1 \le \log n! \le (n + 1)\log \bigg(\frac{{n + 1}}{e}\bigg) + 1. $ Taken from Wikipedia, see here.

EDIT: Actually it is stated in that link "Hence $\log n!$ is $\Theta (n\log n)$''.

EDIT 2: The derivation of the above result is given in the Wikipedia link (and is very elementary). Based on it, let's show that $ \log n! = n \log n - n + O(\log n) \;\; {\rm as}\; n \to \infty, $ which implies, in particular, that $ \log n! \sim n\log n \;\; {\rm as}\; n \to \infty $ (that is, $\log n! / (n\log n) \to 1$ as $n \to \infty$), which implies, in particular, that $\log n!$ is $\Theta (n\log n)$. So, first note that $ n\log n - n + 1 \le \log n! \le (n + 1)\log (n + 1) - (n + 1) + 1. $ Hence, $ n\log n - n + 1 \le \log n! \le n\log (n + 1) + \log (n + 1) - n. $ Next note that, since $\log(1+x) = x + O(x^2)$ as $x \to 0$, $ \log(n+1) - \log n = \log \bigg(\frac{{n + 1}}{n}\bigg) = \log \bigg(1 + \frac{1}{n}\bigg) = \frac{1}{n} + O\bigg(\frac{1}{{n^2 }}\bigg), $ and hence $ \log(n+1) = \log n + \frac{1}{n} + O\bigg(\frac{1}{{n^2 }}\bigg). $ Now, $ n\log n - n + 1 \le \log n! \leq n\bigg[\log n + \frac{1}{n} + O\bigg(\frac{1}{{n^2 }}\bigg)\bigg] + \bigg[\log n + \frac{1}{n} + O\bigg(\frac{1}{{n^2 }}\bigg)\bigg] - n, $ hence $ n\log n - n + 1 \le \log n! \leq n\log n - n + \log n + O(1), $ and finally $ \log n! = n \log n - n + O(\log n). $

3

The easy part is $\log(n!) \le n \log n$, which follows from $n! \le n^n$.

The hard part is discussed in How do you prove that $n^n$ is $O(n!^2)$?.

  • 0
    This is the most simple proof!2011-08-05
1

$e^x = \sum_{n \ge 0} \frac{x^n}{n!}$ implies $e^n \ge \frac{n^n}{n!}$, hence $n! \ge \left( \frac{n}{e} \right)^n$, hence $\log n! \ge n \log n - n$. On the other hand,

$n! \le \left( \frac{1 + 2 + ... + n}{n} \right)^n = \left( \frac{n+1}{2} \right)^n$

by AM-GM, hence $\log n! \le n \log \left( \frac{n+1}{2} \right)$.

  • 0
    Ah, yes, you're right.2011-08-05