What is wrong with this solution for $\mathcal{O}({\log({n \choose \frac{n}{2}})})$?
-
05-11-2019 - |
Pergunta
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.
Nenhuma solução correta