8.1-2

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.

$$lg n!$$ $$lg (n+n-1+..1)$$ $$log n + log (n-1)+...+1$$ above can be written as summation $$\sum_{k = 1}^n lg k$$ lg k is monotonically increasing function and can be bounded by integrals $$ \int_{0}^n log k \leq \sum_{k = 1}^n lg k$$ $$ [k (log k-1)+ck ]_{0}^n \leq \sum_{k = 1}^n lg k$$ $$ [n (log n-1)+cn +0 ] \leq \sum_{k = 1}^n lg k$$ $$ n log n- n + cn \leq \sum_{k = 1}^n lg k$$ $$ \leq n log n $$ $$ = n log n $$