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

Problem Detail: 

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

Asked By : Ghost_Stark

Answered By : D.W.

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 &= \log(1) + \log(2) + \dots + \log(n/2)\\ U &= \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)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47561