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 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)

    “If I die prematurely at any rate I shall be saved from being bored to death at my own success.”
    —Samuel Butler (1835–1902)

    “Although its growth may seem to have been slow, it is to be remembered that it is not a shrub, or plant, to shoot up in the summer and wither in the frosts. The Red Cross is a part of us—it has come to stay—and like the sturdy oak, its spreading branches shall yet encompass and shelter the relief of the nation.”
    —Clara Barton (1821–1912)

    “This was the Eastham famous of late years for its camp- meetings, held in a grove near by, to which thousands flock from all parts of the Bay. We conjectured that the reason for the perhaps unusual, if not unhealthful development of the religious sentiment here, was the fact that a large portion of the population are women whose husbands and sons are either abroad on the sea, or else drowned, and there is nobody but they and the ministers left behind.”
    —Henry David Thoreau (1817–1862)