Editing Stirling's approximation (section)

{{short description|Approximation for factorials}}
[[File:Mplwp factorial gamma stirling.svg|thumb|right|upright=1.35|Comparison of Stirling's approximation with the factorial]]
In [[mathematics]], '''Stirling's approximation''' (or '''Stirling's formula''') is an [[Asymptotic analysis|asymptotic]] approximation for [[factorial]]s. It is a good approximation, leading to accurate results even for small values of <math>n</math>. It is named after [[James Stirling (mathematician)|James Stirling]], though a related but less precise result was first stated by [[Abraham de Moivre]].{{r|dutka|LeCam1986|Pearson1924}}

One way of stating the approximation involves the [[logarithm]] of the factorial:
<math display=block>\ln(n!) = n\ln n - n +O(\ln n),</math>
where the [[big O notation]] means that, for all sufficiently large values of <math>n</math>, the difference between <math>\ln(n!)</math> and <math>n\ln n-n</math> will be at most proportional to the logarithm of <math>n</math>. In computer science applications such as the [[Comparison sort#Number of comparisons required to sort a list|worst-case lower bound for comparison sorting]], it is convenient to instead use the [[binary logarithm]], giving the equivalent form
<math display=block>\log_2 (n!) = n\log_2 n - n\log_2 e +O(\log_2 n).</math> The error term in either base can be expressed more precisely as <math>\tfrac12\log_2(2\pi n)+O(\tfrac1n)</math>, corresponding to an approximate formula for the factorial itself,
<math display=block>n! \sim \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n.</math>
Here the sign <math>\sim</math> means that the two quantities are asymptotic, that is, their ratio tends to 1 as <math>n</math> tends to infinity.