How to prove Big-O when $F(N)$ is even or odd If I'm given a function $f(n)$ which is for example $4n+1$ when even and $3n^2+2$ when odd and I have to prove or disprove $f(n)$ is $\mathcal O( n^2 )$. Do I have to do $f(n) &lt; c n^2$ for all $n &gt; n0$ for both expressions or do I just select the $3n^2+2$ expression?
you have to do for both expressions. But in this case, one expression is strictly smaller than the other one, so you can do it just for the $3n^2+2$ and say $4n+1&lt;3n^2+2$ and therefore also $4n+1&lt;cn^2$.