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) < c n^2$ for all $n > n0$ for both expressions or do I just select the $3n^2+2$ expression?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
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<3n^2+2$ and therefore also $4n+1<cn^2$.
