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 of, rate, growth and/or large:
“At this very moment,... the most frightful horrors are taking place in every corner of the world. People are being crushed, slashed, disembowelled, mangled; their dead bodies rot and their eyes decay with the rest. Screams of pain and fear go pulsing through the air at the rate of eleven hundred feet per second. After travelling for three seconds they are perfectly inaudible. These are distressing facts; but do we enjoy life any the less because of them? Most certainly we do not.”
—Aldous Huxley (1894–1963)
“This is the essential distinction—even opposition—between the painting and the film: the painting is composed subjectively, the film objectively. However highly we rate the function of the scenario writer—in actual practice it is rated very low—we must recognize that the film is not transposed directly and freely from the mind by means of a docile medium like paint, but must be cut piece-meal out of the lumbering material of the actual visible world.”
—Sir Herbert Read (1893–1968)
“Next to the right of liberty, the right of property is the most important individual right guaranteed by the Constitution and the one which, united with that of personal liberty, has contributed more to the growth of civilization than any other institution established by the human race.”
—William Howard Taft (1857–1930)
“It is surprising on stepping ashore anywhere into this unbroken wilderness to see so often, at least within a few rods of the river, the marks of an axe, made by lumberers who have either camped here or driven logs past in previous springs. You will see perchance where, going on the same errand that you do, they have cut large chips from a tall white pine stump for their fire.”
—Henry David Thoreau (1817–1862)