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:
“If you could choose your parents,... we would rather have a mother who felt a sense of guilt—at any rate who felt responsible, and felt that if things went wrong it was probably her fault—we’d rather have that than a mother who immediately turned to an outside thing to explain everything, and said it was due to the thunderstorm last night or some quite outside phenomenon and didn’t take responsibility for anything.”
—D.W. Winnicott (20th century)
“Here commences what was called, twenty years ago, the best timber land in the State. This very spot was described as “covered with the greatest abundance of pine,” but now this appeared to me, comparatively, an uncommon tree there,—and yet you did not see where any more could have stood, amid the dense growth of cedar, fir, etc.”
—Henry David Thoreau (1817–1862)
“Nowadays almost all man’s improvements, so called, as the building of houses and the cutting down of the forest and of all large trees, simply deform the landscape, and make it more and more tame and cheap.”
—Henry David Thoreau (1817–1862)