# How to prove Big-O when $f(n)$ is defined sectionwise

I'm given a function which is defined based on a condition, for example

$$f(n) = \begin{cases} 4n+1, \ \text{n is even}\\ 3n^2+2, \ \text{n is odd} \end{cases}.$$

I have to prove or disprove that $$f(n)$$ is $$\mathcal{O} (n^2)$$. Do I have to show $$f(n) < c n^2$$ for all $$n > n_0$$ for both expressions or do I just select the $$3n^2+2$$ expression?

Your intuition tells you correctly that it should suffice to check the bound for the term $$3n^2+2$$, since $$3n^2+2$$ dominates the function $$4n+1$$. nir shahar has pointed that out in their answer. However, for a formal proof that $$f(n) = \mathcal{O}(n)$$, you will need to formalize your intuition that $$3n^2+2$$ dominates $$4n+1$$ and you will also have to argue why this reduces your problem to showing $$3n^2+2 < cn^2$$.
I advise you not to prove $$3n^2+2 \ge 4n+1$$ and then use this statement. I think it will be easier to instead prove both $$3n^2+2 \le cn^2$$ and $$4n+1 \le c'n^2$$ for $$n > n_0$$, with suitable constants $$c, c' > 0$$, and $$n_0$$. Then, with $$C = \max(c, c')$$, you will have $$f(n) \le Cn^2$$ for all $$n>n_0$$.
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.