Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Stirling's approximation
Summary
In mathematics, Stirling's approximation (or Stirling's formula) is an approximation for factorials. It is a good approximation, leading to accurate results even for small values of . 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:
where the big O notation means that, for all sufficiently large values of , the difference between and will be at most proportional to the logarithm. In computer science applications such as the worst-case lower bound for comparison sorting, it is convenient to use instead the binary logarithm, giving the equivalent form
The error term in either base can be expressed more precisely as , corresponding to an approximate formula for the factorial itself,
Here the sign means that the two quantities are asymptotic, that is, that their ratio tends to 1 as tends to infinity. The following version of the bound holds for all , rather than only asymptotically:
Roughly speaking, the simplest version of Stirling's formula can be quickly obtained by approximating the sum
with an integral:
The full formula, together with precise estimates of its error, can be derived as follows. Instead of approximating , one considers its natural logarithm, as this is a slowly varying function:
The right-hand side of this equation minus
is the approximation by the trapezoid rule of the integral
and the error in this approximation is given by the Euler–Maclaurin formula:
where is a Bernoulli number, and Rm,n is the remainder term in the Euler–Maclaurin formula. Take limits to find that
Denote this limit as . Because the remainder Rm,n in the Euler–Maclaurin formula satisfies
where big-O notation is used, combining the equations above yields the approximation formula in its logarithmic form:
Taking the exponential of both sides and choosing any positive integer , one obtains a formula involving an unknown quantity .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications (2)
Related concepts (23)
Asymptotic expansion
In mathematics, an asymptotic expansion, asymptotic series or Poincaré expansion (after Henri Poincaré) is a formal series of functions which has the property that truncating the series after a finite number of terms provides an approximation to a given function as the argument of the function tends towards a particular, often infinite, point. Investigations by revealed that the divergent part of an asymptotic expansion is latently meaningful, i.e. contains information about the exact value of the expanded function.
Stirling's approximation
In mathematics, Stirling's approximation (or Stirling's formula) is an approximation for factorials. It is a good approximation, leading to accurate results even for small values of . 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: where the big O notation means that, for all sufficiently large values of , the difference between and will be at most proportional to the logarithm.
Time complexity
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.
Related courses (12)
MATH-250: Numerical analysis
Construction and analysis of numerical methods for the solution of problems from linear algebra, integration, approximation, and differentiation.
PHYS-441: Statistical physics of biomacromolecules
Introduction to the application of the notions and methods of theoretical physics to problems in biology.
PHYS-325: Introduction to plasma physics
Introduction à la physique des plasmas destinée à donner une vue globale des propriétés essentielles et uniques d'un plasma et à présenter les approches couramment utilisées pour modéliser son comport
Related lectures (197)
Plasma Physics: Collisions and Resistivity
Covers Coulomb collisions and resistivity in plasma, highlighting their random walk nature.
Mixing Properties of Infinite Measure Preserving Systems
Explores mixing properties of infinite measure preserving systems, focusing on suspensions, Govers transformations, and Lorentz gas.
Taylor Series: Expansion and Properties
Explores Taylor series expansion, derivatives, uniqueness, and applications in function approximation.