Show $\frac{n}{2} \log(n!) = \Omega (n^2 \log(n))$

Question

I am trying to show that $\frac{n}{2} \log(n!) = \Omega (n^2 \log(n))$ but I seem to get a conflicting result.

What i did is:

$n!=1*2*3*...*n \leq n*n*n*...*n=n^n$, so

$\frac{n}{2} \log(n!) \leq \frac{n}{2} \log(n^n) = \frac{n^2}{2} \log(n) \leq n^2 \log(n)$

And so the conclusion you come to is that $\frac{n}{2} \log(n!) = O(n^2 \log(n))$

What am I doing wrong?

Answer 1

The fact that $$\log(n!)=O(n\log n)\tag{1}$$ does not conflict with the fact that $$\log(n!)=\Omega(n\log n).\tag{2}$$ They simply give, together, $\log(n!)=\Theta(n\log n)$.

In order to prove $(1)$ and $(2)$ simultaneously, notice that, by partial summation: $$\log(n!)=\sum_{j=1}^{n}\log j = n\log n-\sum_{j=1}^{n-1}j\log\left(1+\frac{1}{j}\right)\tag{3}$$ but since $\log(1+x)\leq x$ for any $x\in\mathbb{R}^+$, the last sum is bounded by $n-1=o(n\log n)$.

---

In order to prove $(2)$ by avoiding partial summation, you can just notice that: $$(k+1)\log(k+1) - k\log k = k\log(1+1/k)+\log(k+1) \leq 1+\log(k+1)$$ hence: $$\begin{eqnarray*}\log(n!)=\sum_{k=1}^{n-1}\log(k+1)&\geq& 1-n+\sum_{k=1}^{n-1}\left((k+1)\log(k+1) - k\log k\right)\\&=&1-n+n\log n=\Omega(n\log n).\end{eqnarray*}$$