2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – ubadub Mar 21 at 4:12
  • 1
    $\begingroup$ 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)$? $\endgroup$ – ubadub Mar 21 at 4:18
  • 1
    $\begingroup$ 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. $\endgroup$ – Apass.Jack Mar 21 at 4:22
2
$\begingroup$

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?.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ubadub Mar 21 at 4:05
  • 1
    $\begingroup$ @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! $\endgroup$ – D.W. Mar 21 at 4:44

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.