Why is it that O(N + P) where P < N/2 reduces to O(N)?
In the Big-O notation, constant factors are irrelevant.

Then if $N&gt;P$, $O(N+P)$ reduces to $O(N)$, by swapping $N$ and $P$ we have that if $P&gt;N$, $O(N+P)$ reduces to $O(P)$.