Proving Assymptotic tight bound on $\lg(n!)$ is equivalent to $n\lg(n)$ without using Stirling's Approximation.

Question

So, how I did it is by expanding $f(n)=\lg(n!)$ to first \begin{align} \lg(n!) &= \lg(n(n-1)(n-2)\cdot\ldots\cdot2\cdot 1)\\ &=\lg(n)+\lg(n-1)+\lg(n-2)+...+\lg(1)\\ n\lg(n) &\geq \lg(n)+\lg(n-1)+\lg(n-2)+...+\lg(1) \end{align} thus, $f(n) = O(n\lg(n))$.

Then \begin{align} f(n) &= \lg(n)+\lg(n-1)+\ldots+\lg(n/2)+\lg(n/2-1)+...\lg(1)\\ \lg(n)+\lg(n-1)+\ldots+\lg(n/2+1) &\geq n/2\lg(n/2)\\ f(n) &\geq n/2\lg(n/2) \end{align} and thus $f(n) = Ω(n/2\lg(n/2)) \Rightarrow f(n) = Ω(n\lg(n))$

as, $f(n) = O(n\lg(n))$ , $f(n)= Ω(n\lg(n)$, $f(n) = \Theta(n\lg(n))$

Is this would be the correct way of proving $f(n)=\Theta(n\lg(n))$, where $f(n)=\lg(n!)$ without using Stirling's Approximation.

Answer 1

Yes, your derivation is correct. Well done!