I'm asked to evaluate this: $ \mathcal{O} \bigg( \log_2 \binom{n}{n/2} \bigg) $.
I played with this a bit and I keep getting $\mathcal{O} (n\log n)$.
When I substitute $n! = \sqrt{2\pi n} \Big(\dfrac{n}{e}\Big)^n $ I get $\mathcal{O}(n)$, which is the correct answer.
Can you please tell me how to do it without using the above substitution?
Best Answer
I assume that $n=2k$.
Note that $\log_2\binom{n}{n/2}=O\left(\log\binom{n}{n/2}\right)$ by the change-of-base formula for logarithms. Thus, we just need to show that $$\log\binom{n}{n/2}=O(n).$$ Using Riemann-Stieltjes integration, we can show that $$\log(n!)=\sum_{j=1}^n\log(j)=n\log n-n+O(\log n).\tag{1}$$ This is actually stronger than what we need; we only need that $\log(n!)=n\log n+O(n)$. As such, we'll use the weaker statement in what follows.
Using $(1)$, the definition of the binomial, and the property of logarithms that $\log(a/b)=\log(a)-\log(b)$, we can show that for $n=2k$, $$\log\binom{n}{n/2}=\log\left(\frac{(2k)!}{(k!)^2}\right)=2k\log(2k)-2k\log(k)+O(k)=O(n).$$