0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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$.

Maybe this way will cost you two more lines of a proof, but you will be rewarded with a more straight-forward proof.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.