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 large n, rate, growth and/or large:
“Always in England if you had the type of brain that was capable of understanding T.S. Eliot’s poetry or Kant’s logic, you could be sure of finding large numbers of people who would hate you violently.”
—D.J. Taylor (b. 1960)
“At the rate science proceeds, rockets and missiles will one day seem like buffalo—slow, endangered grazers in the black pasture of outer space.”
—Bernard Cooper (b. 1936)
“That land is like an Eagle, whose young gaze
Feeds on the noontide beam, whose golden plume
Floats moveless on the storm, and in the blaze
Of sunrise gleams when Earth is wrapped in gloom;
An epitaph of glory for the tomb
Of murdered Europe may thy fame be made,
Great People! as the sands shalt thou become;
Thy growth is swift as morn, when night must fade;
The multitudinous Earth shall sleep beneath thy shade.”
—Percy Bysshe Shelley (1792–1822)
“It might be seen by what tenure men held the earth. The smallest stream is mediterranean sea, a smaller ocean creek within the land, where men may steer by their farm bounds and cottage lights. For my own part, but for the geographers, I should hardly have known how large a portion of our globe is water, my life has chiefly passed within so deep a cove. Yet I have sometimes ventured as far as to the mouth of my Snug Harbor.”
—Henry David Thoreau (1817–1862)