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

Proof of the upper bound of equation (1).

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

Proof of the lower bound of equation (2).

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

Proof of bound for $\log n!$, equation (3).

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. , second edition. MIT Press, 2001.
• 2 Michael Spivak. Calculus, third edition. Publish or Perish, 1994.
Title asymptotic bounds for factorial AsymptoticBoundsForFactorial 2013-03-22 15:54:25 2013-03-22 15:54:25 stevecheng (10074) stevecheng (10074) 7 stevecheng (10074) Result msc 41A60 msc 68Q25 StirlingsApproximation GrowthOfExponentialFunction