structural:scholar_edition
Growth and approximation

As a function of n {\displaystyle n}, the factorial has faster than exponential growth, but grows more slowly than a double exponential function. Its growth rate is similar to n n {\displaystyle n^{n}}, but slower by an exponential factor. One way of approaching this result is by taking the natural logarithm of the factorial, which turns its product formula into a sum, and then estimating the sum by an integral: ln n ! = ∑ x = 1 n ln x ≈ ∫ 1 n ln x d x = n ln n − n + 1. {\displaystyle \ln n!=\sum _{x=1}^{n}\ln x\approx \int _{1}^{n}\ln x\,dx=n\ln n-n+1.} Exponentiating the result (and ignoring the negligible + 1 {\displaystyle +1} term) approximates n ! {\displaystyle n!} as (n / e) n {\displaystyle (n/e)^{n}}. More carefully bounding the sum both above and below by an integral, using the trapezoid rule, shows that this estimate needs a correction factor proportional to n {\displaystyle {\sqrt {n}}}. The constant of proportionality for this correction can be found from the Wallis product, which expresses π {\displaystyle \pi } as a limiting ratio of factorials and powers of two. The result of these corrections is Stirling's approximation: n ! ∼ 2 π n (n e) n. {\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\,.} Here, the ∼ {\displaystyle \sim } symbol means that, as n {\displaystyle n} goes to infinity, the ratio between the left and right sides approaches one in the limit.Stirling's formula provides the first term in an asymptotic series that becomes even more accurate when taken to greater numbers of terms: n ! ∼ 2 π n (n e) n (1 + 1 12 n + 1 288 n 2 − 139 51840 n 3 − 571 2488320 n 4 + ⋯). {\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\left(1+{\frac {1}{12n}}+{\frac {1}{288n^{2}}}-{\frac {139}{51840n^{3}}}-{\frac {571}{2488320n^{4}}}+\cdots \right).} An alternative version uses only odd exponents in the correction terms: n ! ∼ 2 π n (n e) n exp (1 12 n − 1 360 n 3 + 1 1260 n 5 − 1 1680 n 7 + ⋯). {\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\exp \left({\frac {1}{12n}}-{\frac {1}{360n^{3}}}+{\frac {1}{1260n^{5}}}-{\frac {1}{1680n^{7}}}+\cdots \right).} Many other variations of these formulas have also been developed, by Srinivasa Ramanujan, Bill Gosper, and others.

The binary logarithm of the factorial, used to analyze comparison sorting, can be very accurately estimated using Stirling's approximation. In the formula below, the O (1) {\displaystyle O(1)} term invokes big O notation. log 2 n ! = n log 2 n − (log 2 e) n + 1 2 log 2 n + O (1). {\displaystyle \log _{2}n!=n\log _{2}n-(\log _{2}e)n+{\frac {1}{2}}\log _{2}n+O(1).}