asymptotic bounds for factorial
Stirling’s formula^{} furnishes the following asymptotic bound for the factorial:
$n!=\sqrt{2\pi}{n}^{n+1/2}{e}^{-n}\left(1+\mathrm{\Theta}(\frac{1}{n})\right),n\to \mathrm{\infty}.$ |
The following less precise bounds are useful for counting purposes in computer science:
$n!$ | $=o({n}^{n})$ | (1) | ||
$n!$ | $$ | (2) | ||
$\mathrm{log}n!$ | $=\mathrm{\Theta}(n\mathrm{log}n)$ | (3) |
($o$, $\omega $, and $\mathrm{\Theta}$ are Landau notation.)
Proof of the upper bound of equation (1).
We must show that for every $\epsilon >0$, we have
$$n!\le \epsilon {n}^{n}\mathit{\hspace{1em}}\text{for large enough}n\text{.}$$ |
To see this, write
$n!$ | $=\underset{\u23df}{\sqrt{2\pi}{\displaystyle \frac{\sqrt{n}}{{e}^{n}}}\left(1+O(\frac{1}{n})\right)}{n}^{n},$ |
and observe that the middle quantity tends to $0$ as $n\to \mathrm{\infty}$, so it can be made smaller than any fixed $\epsilon $ by taking $n$ large. ∎
Proof of the lower bound of equation (2).
We are to show that for every $C>0$, we have
$$n!\ge C{n}^{\lambda n}\mathit{\hspace{1em}}\text{for large enough}n\text{.}$$ |
We write:
$n!$ | $=\underset{\u23df}{\sqrt{2\pi n}\left(1+O(\frac{1}{n})\right){\left({\displaystyle \frac{n}{{e}^{1/(1-\lambda )}}}\right)}^{(1-\lambda )n}}{n}^{\lambda n},$ |
and the middle expression can be made to be $\ge C$ by taking $n$ to be large. ∎
Proof of bound for $\mathrm{log}\mathit{}n\mathrm{!}$, equation (3).
Showing $\mathrm{log}n!=O(n\mathrm{log}n)$ is simple:
$n!$ | $=n(n-1)\mathrm{\cdots}(2)(1)\le {n}^{n}$ | ||
$\mathrm{log}n!$ | $\le n\mathrm{log}n$ |
for all $n\ge 1$.
To show $\mathrm{log}n!=\mathrm{\Omega}(n\mathrm{log}n)$, we can take equation (2) with the constants $C=1$ and $\lambda =\frac{1}{2}$. Then
$\mathrm{log}n!\ge \frac{1}{2}n\mathrm{log}n$ |
for large enough $n$. In fact, it may be checked that $n\ge 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 |