Why is it that O(N + P) where P < N/2 reduces to O(N)? My book says that 


  If $P &lt; N/2$ then we know that N is the dominant term so we an drop the $O(P )$."


If it was $O(N + P)$ where $P &gt; N/2$ what would it reduce to?
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)$.