Factorial - Rate of Growth and Approximations For Large N

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)

\log n! \approx n\log n - n + \frac {\log(n(1+4n(1+2n)))} {6} + \frac {\log(\pi)} {2} = n\log n - n + \frac {\log(1 +1/(2n) +1/(8n^2))} {6} + \frac {3\log (2n)} 6 + \frac {\log(\pi)} {2},

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:

    “We all run on two clocks. One is the outside clock, which ticks away our decades and brings us ceaselessly to the dry season. The other is the inside clock, where you are your own timekeeper and determine your own chronology, your own internal weather and your own rate of living. Sometimes the inner clock runs itself out long before the outer one, and you see a dead man going through the motions of living.”
    —Max Lerner (b. 1902)

    “It is in the comprehension of the physically disabled, or disordered ... that we are behind our age.... sympathy as a fine art is backward in the growth of progress ...”
    —Elizabeth Stuart Phelps (1844–1911)

    “Frequently also some fair-weather finery ripped off a vessel by a storm near the coast was nailed up against an outhouse. I saw fastened to a shed near the lighthouse a long new sign with the words “ANGLO SAXON” on it in large gilt letters, as if it were a useless part which the ship could afford to lose, or which the sailors had discharged at the same time with the pilot. But it interested somewhat as if it had been a part of the Argo, clipped off in passing through the Symplegades.”
    —Henry David Thoreau (1817–1862)