6
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ Concisely: ​ 1/2 is the simplest number in the interval (0,1). ​ ​ ​ ​ $\endgroup$ – user12859 Sep 26 '15 at 9:31
  • $\begingroup$ @RickyDemer So what? Splitting the sum as $\log 1 + \dots + \log cn + \dots + \log n$ for any $0<c<1$ would work just as well. $\endgroup$ – David Richerby Sep 26 '15 at 10:17
11
$\begingroup$

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)$.

$\endgroup$
  • 1
    $\begingroup$ Ok I think I'm starting to understand, but first, what is stopping me from not breaking up the sum into two parts and just lower bounding each term in the sum? Like this: log(1) + log(1) + ... + log(1) n times. $\endgroup$ – David Velasquez Sep 26 '15 at 5:21
  • 1
    $\begingroup$ @Ghost_Stark, you can do that. That gives you the lower bound $S \ge 0$, which is a valid lower bound, but not very useful. (The lower bound $S \ge -42$ is also true, but even less useful.) It's just like if I tell you I'm thinking of a number between 1 and 100, and you ask for a hint, and I tell you: well, it's larger than $0$. You probably won't be amused at my useless hint, as you already knew that. It's the same for what you want to do. There are many lower bounds that one can prove -- the trick is to find one that is strong enough to prove what you want to prove. $\endgroup$ – D.W. Sep 26 '15 at 5:23
  • 1
    $\begingroup$ Ah I understand now! Thanks for the answer and the explanation! Very helpful. I guess my problem was not understanding that you have to have a reasonable lower bound to look for. $\endgroup$ – David Velasquez Sep 26 '15 at 5:31
4
$\begingroup$

$\dfrac n2$ is chosen so that you have sufficiently many factors ($O(n)$) that are sufficiently large ($O(n)$), so that the product remains $\sim n^n$ while being a lower bound to $n!$

$\endgroup$
2
$\begingroup$

The intuition is that $\log x$ is slowly-growing, and consequently "most" of the terms will be around $\log n$ in size.

More precisely, if there are $\Theta(n)$ terms that are all $\Theta(\log n)$ in size, then their sum will indeed be $\Theta(n \log n)$ and we can conclude $\log n! \in \Omega(n \log n)$.

Taking half of the terms is merely the simplest idea to describe and calculate, and fortunately it satisfies the needed conditions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.