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:
“The newspapers, especially those in the East, are amazingly superficial and ... a large number of news gatherers are either cynics at heart or are following the orders and the policies of the owners of their papers.”
—Franklin D. Roosevelt (18821945)
“Unless a group of workers know their work is under surveillance, that they are being rated as fairly as human beings, with the fallibility that goes with human judgment, can rate them, and that at least an attempt is made to measure their worth to an organization in relative terms, they are likely to sink back on length of service as the sole reason for retention and promotion.”
—Mary Barnett Gilson (1877?)
“This [new] period of parenting is an intense one. Never will we know such responsibility, such productive and hard work, such potential for isolation in the caretaking role and such intimacy and close involvement in the growth and development of another human being.”
—Joan Sheingold Ditzion and Dennie Palmer (20th century)
“Friends serve central functions for children that parents do not, and they play a critical role in shaping childrens social skills and their sense of identity. . . . The difference between a child with close friendships and a child who wants to make friends but is unable to can be the difference between a child who is happy and a child who is distressed in one large area of life.”
—Zick Rubin (20th century)
