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! &amp;= \log(1 \cdot 2 \cdot 3 \cdots n  )\\  
&amp;= \log 1 + \log2 + \log3 + \dots + \log n \\  
&amp;= \log 1  + \dots + \log\tfrac{n}{2} + \dots + \log n\\  
&amp;\geq \log\tfrac{n}{2} + \log\big(\tfrac{n}{2} + 1\big) + \dots + \log n &amp;&amp;\text{(i.e., the larger half of the sum)}\\
&amp;\geq \log\big(\tfrac{n}{2}\big) + \log\big(\tfrac{n}{2}\big) + \dots + \log\big(\tfrac{n}{2}\big)&amp;&amp;\text{(adding $\tfrac{n}2$ times)}  \\
&amp;= \log\big(\tfrac{n}{2} \cdot \tfrac{n}{2} \cdots \tfrac{n}{2}) &amp;&amp;\text{($\tfrac{n}{2}$ times)}  \\
&amp;= \log\Big(\tfrac{n}{2}^{\tfrac{n}{2}}\Big)\\  
&amp;= \tfrac{n}{2} log\big(\tfrac{n}{2}\big) &amp;&amp;\text{(by log exponent rule)}
\end{align*}$$

Thus, $\log(n!) \geq \tfrac{n}{2}\log\big(\tfrac{n}{2}\big)$, so we conclude that $\log(n!) = \Omega(n\log 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\log  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!
Consider the sum $S = \log(1) + \dots + \log(n)$.  We're going to break it into two parts: $S=T+U$, where

\begin{align*}
T &amp;= \log(1) + \log(2) + \dots + \log(n/2)\\
U &amp;= \log(n/2+1) + \dots + \log(n-1) + \log(n).
\end{align*}

Basically, $T$ has the first $n/2$ terms of $S$, and $U$ has the remaining $n/2$ terms.

Now we'll lower-bound each of them.  Start with $T$.  Each term in $T$ is at least $\log(1)$, so we get

$$T \ge \log(1) + \log(1) + \dots + \log(1) = 0 + 0 + \dots 0,$$

so $T \ge 0$.  Next look at $U$.  Each term in $U$ is at least $\log(n/2)$, so we get

$$U \ge \log(n/2) + \log(n/2) + \dots + \log(n/2) = (n/2) \times \log(n/2).$$

Now $S = T+U$, so plugging in the lower bounds obtained above, it follows that

$$S =T+U\ge 0 + (n/2) \times \log(n/2).$$

This is exactly the result you wanted to prove.  Also, $(n/2) \times \log(n/2)$ is $\Omega(n \log n)$, so this proves that the sum $S$ is $\Omega(n \log n)$.