asymptotic bounds for factorial
Stirling’s formula furnishes the following asymptotic bound for the factorial:
The following less precise bounds are useful for counting purposes in computer science:
(, , and are Landau notation.)
Proof of the upper bound of equation (1).
We must show that for every , we have
To see this, write
and observe that the middle quantity tends to as , so it can be made smaller than any fixed by taking large. ∎
Proof of the lower bound of equation (2).
We are to show that for every , we have
and the middle expression can be made to be by taking to be large. ∎
Proof of bound for , equation (3).
Showing is simple:
for all .
To show , we can take equation (2) with the constants and . Then
for large enough . In fact, it may be checked that suffices. ∎
|Title||asymptotic bounds for factorial|
|Date of creation||2013-03-22 15:54:25|
|Last modified on||2013-03-22 15:54:25|
|Last modified by||stevecheng (10074)|