Stirling's approximation

In mathematics, Stirling's approximation (or Stirling's formula) is an asymptotic approximation for factorials. It is a good approximation, leading to accurate results even for small values of n {\displaystyle n} . It is named after James Stirling, though a related but less precise result was first stated by Abraham de Moivre. One way of stating the approximation involves the logarithm of the factorial: ln ⁡ n ! = n ln ⁡ n − n + O ( ln ⁡ n ) , {\displaystyle \ln n!=n\ln n-n+O(\ln n),} where the big O notation means that, for all sufficiently large values of n {\displaystyle n} , the difference between ln ⁡ n ! {\displaystyle \ln n!} and n ln ⁡ n − n {\displaystyle n\ln n-n} will be at most proportional to the logarithm of n {\displaystyle n} . In computer science applications such as the worst-case lower bound for comparison sorting, it is convenient to instead use the binary logarithm, giving the equivalent form log 2 ⁡ n ! = n log 2 ⁡ n − n log 2 ⁡ e + O ( log 2 ⁡ n ) . {\displaystyle \log _{2}n!=n\log _{2}n-n\log _{2}e+O(\log _{2}n).} The error term in either base can be expressed more precisely as 1 2 log ⁡ ( 2 π n ) + O ( 1 n ) {\displaystyle {\tfrac {1}{2}}\log(2\pi n)+O({\tfrac {1}{n}})} , corresponding to an approximate formula for the factorial itself, n ! ∼ 2 π n ( n e ) n . {\displaystyle n!\sim {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}.} Here the sign ∼ {\displaystyle \sim } means that the two quantities are asymptotic, that is, their ratio tends to 1 as n {\displaystyle n} tends to infinity.