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)
&amp;\ge \log{n} + \log{(n-1)} + \ldots + \log(n/2)\\
&amp;\ge n/2 \log(n/2)\\
&amp;=\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)
&amp;=\log(n!)\\
&amp;\sim \log\left({\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}}\right) \\
&amp;\sim n(\log(n) -1) \\
&amp;\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.$$