What is wrong with this solution for $\mathcal{O}({\log({n \choose \frac{n}{2}})})$?
$\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.$$