# Theory of complexity: What's wrong with this solution for \$ mathcal {O} ({ log ({n choose frac {n} {2}})}) \$?

In this MIT OCW recitation, the instructor uses the Stirling approximation to calculate that

$$mathcal {O} ({ log ({n choose frac {n} {2}})}) = mathcal {O} (n)$$.

However, I followed the following steps to conclude that $$mathcal {O} ({ log ({n choose frac {n} {2}})}) = mathcal {O} ( log {n})$$. What did I do wrong?

First, keep in mind that $${n choose frac {n} {2}} = frac {n!} { frac {n} {2}! frac {n} {2}!}$$. By basic laws of logarithm, we obtain 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's wrong here? I've reviewed it for a while and I can not see any error. However, when plotting these functions, I can clearly see that there must be an error.