asymptotic bounds for factorial

Stirling’s formula furnishes the following asymptotic bound for the factorial:

\displaystyle n!=\sqrt{2\pi}\,n^{n+1/2}e^{-n}\,\bigl{(}1+\Theta(\tfrac{1}{n})% \bigr{)}\,,\quad n\to\infty\,.

The following less precise bounds are useful for counting purposes in computer science:

$\displaystyle n!$	$\displaystyle=o(n^{n})$	(1)
$\displaystyle n!$	$\displaystyle=\omega(n^{\lambda n})\qquad\text{for every $0\leq\lambda<1$}$	(2)
$\displaystyle\log n!$	$\displaystyle=\Theta(n\log n)$	(3)

( $o$ , $\omega$ , and $\Theta$ are Landau notation.)

We must show that for every $\varepsilon>0$ , we have

n!\leq\varepsilon\,n^{n}\quad\text{for large enough $n$.}

To see this, write

\displaystyle n!

\displaystyle=\underbrace{\sqrt{2\pi}\,\frac{\sqrt{n}}{e^{n}}\,\bigl{(}1+O(% \tfrac{1}{n})\bigr{)}}\,n^{n}\,,

and observe that the middle quantity tends to $0$ as $n\to\infty$ , so it can be made smaller than any fixed $\varepsilon$ by taking $n$ large. ∎

We are to show that for every $C>0$ , we have

n!\geq C\,n^{\lambda n}\quad\text{for large enough $n$.}

We write:

\displaystyle n!

\displaystyle=\underbrace{\sqrt{2\pi n}\,\bigl{(}1+O(\tfrac{1}{n})\bigr{)}% \left(\frac{n}{e^{1/(1-\lambda)}}\right)^{(1-\lambda)n}}\,n^{\lambda n}\,,

and the middle expression can be made to be $\geq C$ by taking $n$ to be large. ∎

Showing $\log n!=O(n\log n)$ is simple:

	$\displaystyle n!$	$\displaystyle=n(n-1)\cdots(2)(1)\leq n^{n}$
	$\displaystyle\log n!$	$\displaystyle\leq n\log n$

for all $n\geq 1$ .

To show $\log n!=\Omega(n\log n)$ , we can take equation (2) with the constants $C=1$ and $\lambda=\tfrac{1}{2}$ . Then

\displaystyle\log n!\geq\tfrac{1}{2}\,n\log n

for large enough $n$ . In fact, it may be checked that $n\geq 1$ suffices. ∎

References

1 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, second edition. MIT Press, 2001.
2 Michael Spivak. Calculus, third edition. Publish or Perish, 1994.

Title	asymptotic bounds for factorial
Canonical name	AsymptoticBoundsForFactorial
Date of creation	2013-03-22 15:54:25
Last modified on	2013-03-22 15:54:25
Owner	stevecheng (10074)
Last modified by	stevecheng (10074)
Numerical id	7
Author	stevecheng (10074)
Entry type	Result
Classification	msc 41A60
Classification	msc 68Q25
Related topic	StirlingsApproximation
Related topic	GrowthOfExponentialFunction