Obtain asymptotically tight bounds on \(\lg(n!)\) without using Stirling’s approximation. Instead, evaluate the summation \(\sum_{k=1}^{n} \lg k\) using techniques from Section A.2.
We want to find tight bounds on \(\lg(n!)\). Since \(n! = 1 \cdot 2 \cdot 3 \cdots n\), taking logarithms gives us \(\lg(n!) = \sum_{k=1}^{n} \lg k\). Intuitively, roughly half of these terms (the upper half, from \(\lceil n/2 \rceil\) to \(n\)) are each at least \(\lg(n/2)\), so the sum should be at least around \((n/2) \lg n\). This suggests \(\Theta(n \lg n)\), which we now confirm by bounding the summation from both sides.
For the lower bound, consider only the upper half of the sum:
\[\begin{align*} \lg(n!) &= \sum_{k=1}^{n} \lg k \\ &\geq \sum_{k=\lceil n/2 \rceil}^{n} \lg k \\ &\geq \sum_{k=\lceil n/2 \rceil}^{n} \lg(n/2) \\ &= (n - \lceil n/2 \rceil + 1) \lg(n/2) \\ &\geq \frac{n}{2} \cdot (\lg n - 1) \\ &= \frac{n \lg n}{2} - \frac{n}{2} \\ &= \Omega(n \lg n) \end{align*}\]
For the upper bound, we can bound each term from above using \(\lg k \leq \lg n\) for \(k \leq n\):
\[\begin{align*} \lg(n!) &= \sum_{k=1}^{n} \lg k \\ &\leq \sum_{k=1}^{n} \lg n \\ &= n \lg n \\ &= O(n \lg n) \end{align*}\]Combining both bounds, we get \(\lg(n!) = \Theta(n \lg n)\).