Problem Detail: So I was able to show that: $log(n!) = O(nlog n)$ without any problems. My question is when trying to prove that $log (n!) = Omega(nlog 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 + logtfrac{n}{2} + dots + log n &geq logtfrac{n}{2} + logbig(tfrac{n}{2} + 1big) + dots + log n &&text{(i.e., the larger half of the sum)} &geq logbig(tfrac{n}{2}big) + logbig(tfrac{n}{2}big) + dots + logbig(tfrac{n}{2}big)&&text{(adding $tfrac{n}2$ times)} &= logbig(tfrac{n}{2} cdot tfrac{n}{2} cdots tfrac{n}{2}) &&text{($tfrac{n}{2}$ times)} &= logBig(tfrac{n}{2}^{tfrac{n}{2}}Big) &= tfrac{n}{2} logbig(tfrac{n}{2}big) &&text{(by log exponent rule)} end{align*}$$ Thus, $log(n!) geq tfrac{n}{2}logbig(tfrac{n}{2}big)$, so we conclude that $log(n!) = Omega(nlog 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(nlog 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!
$$begin{align*} log n! &= log(1 cdot 2 cdot 3 cdots n ) &= log 1 + log2 + log3 + dots + log n &= log 1 + dots + logtfrac{n}{2} + dots + log n &geq logtfrac{n}{2} + logbig(tfrac{n}{2} + 1big) + dots + log n &&text{(i.e., the larger half of the sum)} &geq logbig(tfrac{n}{2}big) + logbig(tfrac{n}{2}big) + dots + logbig(tfrac{n}{2}big)&&text{(adding $tfrac{n}2$ times)} &= logbig(tfrac{n}{2} cdot tfrac{n}{2} cdots tfrac{n}{2}) &&text{($tfrac{n}{2}$ times)} &= logBig(tfrac{n}{2}^{tfrac{n}{2}}Big) &= tfrac{n}{2} logbig(tfrac{n}{2}big) &&text{(by log exponent rule)} end{align*}$$ Thus, $log(n!) geq tfrac{n}{2}logbig(tfrac{n}{2}big)$, so we conclude that $log(n!) = Omega(nlog 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(nlog 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+Uge 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
