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