Prove $f(n)=O(n^2)$

Question

I have to prove that the function $f(n)=3n^2-n+4$ is $O(n^2)$. So I use the definition of big oh:

$f(n)$ is big oh $g(n)$ if there exist an integer $n_0$ and a constant $c>0$ such that for all integers $n\geq n_0$, $f(n)\leq cg(n)$.

And it doesn't matter what those constants are. So I will choose $c=1$

\begin{align} f(n)&\leq cg(n)\\ 3n^2-n+4&\leq 1*n^2\\ 3n^2-n+4&\leq n^2\\ 0&\leq n^2-3n^2+n-4\\ 0&\leq -2n^2+n-4 \end{align}

Now I am having trouble figuring out $n_0$ from here. In the book he simplified the polynomial to its roots and logically determined $n_0$. It looks like this polynomial can't be broken down into a $(a\pm b)(c\pm d)$ form.

Answer 1

If you let $c = 1$, then you're essentially saying that for large enough $n$, it is true that $f(n) \leq g(n)$. In other words, you're saying that $3n^2 - n + 4 \leq n^2$ for large enough $n$. But clearly that's not true; as $n$ grows, $3n^2 + O(n)$ will tend to $3$ times large than $n^2$.

Instead, let $c = 4$ (or anything not less than $3$). Then you're saying that for large enough $n$, $3n^2 - n + 4 \leq 4 \cdot n^2$. This plot may help to visualize it.

Can you take it from here?

Answer 2

It does matter what the constants are. In this case, $c=3$ and $n_0 = 5$ should suffice. Note that if $n \geq 5$, then $-n+4 < 0$. Then, $$3n^2-n+4 < 3n^2$$ for all $n \geq 5$, and so, we can conclude that the given function is $O(n^2)$.