2 ms·
A quick and dirty approximation of the number of digits in n! is n lg n, which approximates n! from above, via the inequality 1 * 2 * … * n ≤ n * … * n. (Th
by Sharlin 22d ago
A quick and dirty approximation of the number of digits in n! is n lg n, which approximates n! from above, via the inequality
1 * 2 * … * n ≤ n * … * n.
(This approximation should be familiar to many from an algorithmics class.)
For a tighter bound, use n lg n - n/2, or a better approximation of ln 10 in place of 1/2 if you wish. This comes from Stirling's approximation which notes that
ln n! = n ln n - n + O(ln n).
- qsort 22d ago> (This approximation should be familiar to many from an algorithmics class.) You need both sides though :) What makes it interesting for estimating algorithmic complexity is that \log{n!} \in \Theta(n \log n). One side is obvious as you note, the other less so, but there's a famous trick to do both at once: \log{n!} = \log{\prod_{h=0}^{n} h} = \sum_{h=0}^{n} \log{h} Therefore, \int_0^n \log{x} dx \le \log{n!} \le \int_0^n \log{x+1} dx with both integrals trivial by parts.
- Sharlin 22d agoSure, I could've said "upper bound" :P