# Confused about proof that $\log(n!) = \theta(n\log n)$

So I was able to show that:

$\log(n!) = O(n \log n)$ without any problems.

My question is when trying to prove that $\log (n!) = \Omega(n \log n)$.

I was able to show that:

\begin{align} \log(n!) & = \log(1 \cdot 2 \cdot 3 \cdots n) \\ & = \log(1) + \log(2) + \log(3) + \dots + \log(n) \\ & = \log(1) + \dots + \log\left(\frac{n}{2}\right) + \dots + \log(n) \\ & \geq \log\left(\frac{n}{2}\right)+ \log\left(\frac{n}{2} + 1\right) + \dots + \log(n) \end{align}

(ie, the larger half of the sum)

Note: this is the part I don't fully understand

\begin{align} & \geq \log\left(\frac{n}{2}\right) + \log\left(\frac{n}{2}\right) + \cdots + \log\left(\frac{n}{2}\right) & & \text{(add them $n/2$ times)} \\ & = \log \left(\frac{n}{2} \cdot \frac{n}{2} \cdots \frac{n}{2}\right) & & \left(\frac{n}{2} \text{times}\right) \\ & = \log \left( \frac{n}{2}^{\frac{n}{2}} \right) \\ & = \frac{n}{2} \log \left(\frac{n}{2}\right) & & \text{(by log exponent rule)} \end{align}

Thus,

$\log(n!) \geq \frac{n}{2}\log(\frac{n}{2})$
$\log(n!) = \Omega(n\hspace{3pt}\log\hspace{3pt}n)$

I don't understand how finding the lower bound of $\log(n!)$ is found by getting the larger half of the sum. Why is that chosen to find $\Omega(n\hspace{3pt}\log \hspace{3pt} n)$? I feel like it's probably something obvious but it's the only thing keeping me from fully grasping the proof. If someone can enlighten me, I would appreciate it!

• What exactly don't you understand? All summands are non-negative, so the whole sum is not less than its part. Also $n/2\le n/2+1\le \dots$, this gives the final estimate. Why is this approach chosen? Because it works. – zhoraster Sep 26 '15 at 5:04
• It turns out one can "give away" an awful lot in finding a suitable lower bound. This gives constant $1/2$, and in fact one cannot very much better by trying for a better (greater) lower bound. – André Nicolas Sep 26 '15 at 5:16
• This is a very bad way of cross-posting. – zhoraster Sep 26 '15 at 7:00
• Crossposting is generally frowned upon. If you decide to cross-post anyway, the very least you should to is to clearly indicate that in your post and add the link to the post on the other site. See, for example, this answer. You can find several other discussions about crossposting on meta. – Martin Sleziak Sep 26 '15 at 7:13