Rate of Growth and Approximations For Large N
As n grows, the factorial n! increases faster than all polynomials and exponential functions (but slower than double exponential functions) in n.
Most approximations for n! are based on approximating its natural logarithm
The graph of the function f(n) = log n! is shown in the figure on the right. It looks approximately linear for all reasonable values of n, but this intuition is false. We get one of the simplest approximations for log n! by bounding the sum with an integral from above and below as follows:
which gives us the estimate
Hence log n! is Θ(n log n) (see Big O notation). This result plays a key role in the analysis of the computational complexity of sorting algorithms (see comparison sort). From the bounds on log n! deduced above we get that
It is sometimes practical to use weaker but simpler estimates. Using the above formula it is easily shown that for all n we have, and for all n ≥ 6 we have .
For large n we get a better estimate for the number n! using Stirling's approximation:
In fact, it can be proved that for all n we have
A much better approximation for log n! was given by Srinivasa Ramanujan (Ramanujan 1988)
thus it is even better than the next correction term of Stirling's formula.
Read more about this topic: Factorial
Famous quotes containing the words rate, growth and/or large:
“Strange that the vanity which accompanies beauty—excusable, perhaps, when there is such great beauty, or at any rate understandable—should persist after the beauty was gone.”
—Mary A. [Elizabeth, Countess Von] Arnim (1866–1941)
“A personality is an indefinite quantum of traits which is subject to constant flux, change, and growth from the birth of the individual in the world to his death. A character, on the other hand, is a fixed and definite quantum of traits which, though it may be interpreted with slight differences from age to age and actor to actor, is nevertheless in its essentials forever fixed.”
—Hubert C. Heffner (1901–1985)
“In most nineteenth-century cities, both large and small, more than 50 percent—and often up to 75 percent—of the residents in any given year were no longer there ten years later. People born in the twentieth century are much more likely to live near their birthplace than were people born in the nineteenth century.”
—Stephanie Coontz (20th century)