The $\frac{n}{2}$ bound does not work in general, for example when $n=p^k$ for $p$ an odd prime.