# What is wrong with this solution for $\mathcal{O}({\log({n \choose \frac{n}{2}})})$?

In this recitation on MIT OCW, the instructor uses Stirling's approximation to calculate that

$$\mathcal{O}({\log({n \choose \frac{n}{2}})}) = \mathcal{O}(n)$$.

However, I went through the following steps to conclude that $$\mathcal{O}({\log({n \choose \frac{n}{2}})}) = \mathcal{O}(\log{n})$$. Where did I go wrong?

First, note that $${n \choose \frac{n}{2}} = \frac{n!}{\frac{n}{2}!\frac{n}{2}!}$$. By basic logarithm laws, we get that this is equal to $$\log{(n!)} - \log{(\frac{n}{2}!\frac{n}{2}!)}$$. From this it follows that:

$$\mathcal{O}(\log{(n!)} - \log{(\frac{n}{2}!\frac{n}{2}!)})\\ = \mathcal{O}(\log{(n!)}) \\ = \mathcal{O}\Big(\log{\big(n(n-1)(n-2)\cdots(1)\big)}\Big) \\ = \mathcal{O}\Big(\log{n} + \log{(n-1)} + \ldots + \log{(1))}\Big) = \mathcal{O}(\log{n})$$

So, what is wrong here? I've gone over it for a while and I can't see any mistakes. Plotting these functions, though, I can see quite clearly that there must be a mistake.

$$\mathcal{O}\Big(\log{n} + \log{(n-1)} + \ldots + \log{(1))}\Big) = \mathcal{O}(\log{n})$$

That is not right. When $$n$$ is large enough,

\begin{align} \log{n} + \log{(n-1)} + \ldots + \log(1) &\ge \log{n} + \log{(n-1)} + \ldots + \log(n/2)\\ &\ge n/2 \log(n/2)\\ &=\Theta(n\log n) \end{align}

More precisely, since $$n!\sim {\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}}$$ by Stirling's approximation,

\begin{align} \log{n} + \log{(n-1)} + \ldots + \log(1) &=\log(n!)\\ &\sim \log\left({\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}}\right) \\ &\sim n(\log(n) -1) \\ &\sim n\log(n) \end{align}

You can take a moment to try understanding intuitively why $$\lim_{n\to\infty}\frac {\log(n!)}{\log (n^n)} = 1.$$

• Thank you. However I am a little confused how you got from the 2nd->3rd->4th steps for the first set of equations/inequalities. Could you clarify? – ubadub Mar 21 '19 at 4:12
• Actually I think I figured it out, leaving here for others: the second step comes from the fact that there are $n/2$ log terms before $\log(n/2)$, and $log(n/2)$ is less than or equal to all of them, so $(n/2)log(n/2)$ must be less than or equal to the sum of all the log terms. The third follows from that. However, why are the third and fourth steps necessary? Isn't $(n/2)\log(n/2)$ already $\Theta(n\log n)$? – ubadub Mar 21 '19 at 4:18
• Yes, $(n/2)\log(n/2)=\Theta(n\log n)$. I must have been overly detailed. I was doubling details when you asked. Upon with you "isn't" feedback, I just reduced my verbosity. – John L. Mar 21 '19 at 4:22

The last step is incorrect. $$\mathcal{O}\Big(\log{n} + \log{(n-1)} + \ldots + \log{(1))}\Big)$$ is not $$\mathcal{O}(\log{n})$$. You made the same mistake as What goes wrong with sums of Landau terms?. See also What is the asymptotic runtime of this nested loop?.

• Thanks. That's not me in "What goes wrong with sums of Landau terms?" but I see that it is the same mistake I made. – ubadub Mar 21 '19 at 4:05
• @ubadub, sorry, I phrased that wrong. I didn't mean it was you, I meant they made the same mistake you did (it's an easy mistake to make). I edited my answer. Sorry about that! – D.W. Mar 21 '19 at 4:44