In other words, how to prove this equation
$$\lg{n!} = \Theta(n\lg{n})$$
$\begingroup$
$\endgroup$
4
asked Aug 5, 2011 at 0:36
-
$\begingroup$ Related to math.stackexchange.com/questions/46892/… $\endgroup$– lhfCommented Aug 5, 2011 at 0:51
-
$\begingroup$ Is $\Theta$ the big O? $\endgroup$– user9464Commented Aug 5, 2011 at 1:10
-
$\begingroup$ I'm reading Introduction of Algorithm, $\Theta$ has a different meaning with big O. $\endgroup$– LeafGlowPathCommented Aug 5, 2011 at 1:23
-
2$\begingroup$ $\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)$ $\endgroup$– AryabhataCommented Aug 5, 2011 at 1:43
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
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)$?.
-
$\begingroup$ I had some trouble to go from $n^n = O(n! ^ 2)$ to $n^n = O(n!)$. $\endgroup$ Commented Aug 5, 2011 at 2:04
-
$\begingroup$ @ablmf, you take logs and go from $n^n = O(n! ^ 2)$ to $n\log n = O(\log (n!))$. $\endgroup$– lhfCommented Aug 5, 2011 at 11:51
-
$\begingroup$ This is the most simple proof! $\endgroup$ Commented Aug 5, 2011 at 13:57
$\begingroup$
$\endgroup$
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). $$
$\begingroup$
$\endgroup$
2
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)$.
answered Aug 5, 2011 at 10:35
-
$\begingroup$ Nice! I'm not familiar with the $\Theta$ notation. I suspect your statement to be stronger than the one in the title. Is this correct? $\endgroup$ Commented Aug 5, 2011 at 11:17
-
$\begingroup$ @Pierre-Yves Gaillard: Yes, see here for the definition of various symbols concerning asymptotic behavior: en.wikipedia.org/wiki/Big_O_notation $\endgroup$ Commented Aug 5, 2011 at 11:24
$\begingroup$
$\endgroup$
2
$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)$.
answered Aug 5, 2011 at 3:20
-
$\begingroup$ Isn'it $n\log n-n$ (not $n\log n-1$)? $\endgroup$ Commented Aug 5, 2011 at 10:47
-