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.