> (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:
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.