Do you like factorials?
Probably, you do. If no, whatever, read this post to know how get rid of factorials.
It is Stirling’s approximation or just Stirling’s formula. It allows to replace factorials with their approximation. If you not interested in math, skip to formula usage
Replace factorial with its definition:
\[ln(n!) = ln(1 \cdot 2 \cdot 3 ...)\]Transform logarithm of multiplication to sum of logarithms:
\[ln(1 \cdot 2 \cdot 3 ...) = ln(1) + ln(2) + ln(3) + ... + ln(n)\]Take a look at the integral $\int_a^b f(x) dx$
Replace $f(x)$ with $ln(x)$, $a$ with $1$, and $b$ with $n$. Then use numerical
integration with step 1 and right rectangle rule
Right-hand parts of two previous formulas are equal, with respect $ln(1)=0$. Then:
\[ln(1 \cdot 2 \cdot 3 ...) \approx \int_1^n ln(x) dx\]Calculate integral using integration by parts:
\[\int ln(x) dx = x \cdot ln(x) - \int x d(ln(x)) = x \cdot ln(x) - \int dt = x \cdot ln(x) - x + C\]Applying boundaries [1..n]
yields final result:
\[ln(n!) = n \cdot ln(n) - n + 1\]Exactly what on the top.
It is much simpler proof, with lose of accuracy, but still valid for partial applications.
Replace factorial with its definition:
\[ln(n!) = ln(1 \cdot 2 \cdot 3 ...)\]Transform logarithm of multiplication to sum of logarithms:
\[ln(1 \cdot 2 \cdot 3 ...) = ln(1) + ln(2) + ln(3) + ... = \sum_{i=1}^n ln(i)\]From monotonic property of logarithms $a \leq b \rightarrow ln(a) \leq ln(b)$ take upper bound for each $ln(i)$:
\[\forall i \; ln(i) \leq ln(n)\]Then, using worst case substitution, sum can be rewritten as:
\[\sum_{i=1}^n ln(i) \leq \sum_{i=1}^N ln(n)\]But $ln(n)$ does not depend on i, so get rid of sum:
Done.
No one cares about O(log(n!)) of your algorithm, but everybody
knows that O(n log n), linearithmic complexity,
is very good property of algorithm. By the way, do not scare people with factorial sign.
If you try to calculate ln(n!) with most straightforward implementation
without suitable datatype, you’ll likely get the number overflow exception, in spite
of result value is not very large. For example for n=100 overall result is
approximately 363 (Stirling’s approximation gives 361) where factorial value is $10^{154}$.
As far as I know, calculating factorial is O(n) complexity algorithm,
because we need n multiplications. Using Stirling’s approximation we need to calculate $n^n$ term, that can
be calculated in O(log n) with clever trick
It can be surprising, but factorials defined not only for positive integers.
So, for example 2.5! is completely valid expression. -6! also. They can be calculated
using Gamma-functions for real numbers. Unfortunately, they are
pretty complicated, so people use Stirling’s formula instead.
Almost everything that using factorials can use Stirling’s approximation. Permutations, binomial coefficients, fractals, number theory and a huge amount of topics I’m not aware of.
P.S. Stirling’s formula presented here is rough enough. More accurate formula is \(n! = \sqrt{2\pi} n^{n + 0.5}e^{-n}\). Check its proof here.
mishadoff 23 February 2013