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 large n, rate, growth and/or large:

    “All sailors pause to watch a steamer, and shout in welcome or derision. In one a large Newfoundland dog put his paws on the rail and stood up as high as any of them, and looked as wise. But the skipper, who did not wish to be seen no better employed than a dog, rapped him on the nose and sent him below. Such is human justice!”
    —Henry David Thoreau (1817–1862)

    “If we became students of Malcolm X, we would not have young black men out there killing each other like they’re killing each other now. Young black men would not be impregnating young black women at the rate going on now. We’d not have the drugs we have now, or the alcoholism.”
    —Spike Lee (b. 1956)

    “There are enough fagots and waste wood of all kinds in the forests of most of our towns to support many fires, but which at present warm none, and, some think, hinder the growth of the young wood.”
    —Henry David Thoreau (1817–1862)

    “It is said that the British Empire is very large and respectable, and that the United States are a first-rate power. We do not believe that a tide rises and falls behind every man which can float the British Empire like a chip, if he should ever harbor it in his mind.”
    —Henry David Thoreau (1817–1862)