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
> (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:
Sharlin · · focus · HN ↗
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
qsort · · focus · HN ↗
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 · · focus · HN ↗