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 honor motherhood with glowing sentimentality, but we don’t rate it high on the scale of creative occupations.”
    —Leontine Young (20th century)

    “You know that the nucleus of a time is not
    The poet but the poem, the growth of the mind
    Of the world, the heroic effort to live expressed
    As victory. The poet does not speak in ruins
    Nor stand there making orotund consolations.
    He shares the confusions of intelligence.”
    —Wallace Stevens (1879–1955)

    “Every society consists of men in the process of developing from children into parents. To assure continuity of tradition, society must early prepare for parenthood in its children; and it must take care of the unavoidable remnants of infantility in its adults. This is a large order, especially since a society needs many beings who can follow, a few who can lead, and some who can do both, alternately or in different areas of life.”
    —Erik H. Erikson (1904–1994)