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

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.

• "It doesn't matter what those constants are." Well, it does. You can't just choose $c=1$. The expression $-2n^2+n-4$ is always negative, that's why you can't find the $n_0$ you are looking for. Try $c=3$. Oct 1 '14 at 15:43
• In saying "it doesn't matter what those constants are", you are mis-interpreting the meaning of existential quantifiers. To say "there exists an integer $n_0$ and a constant $c>0$" means that there are certain specific values of $n_0$ and of $c$ which work. It does not mean that any old values of $n_0$ and of $c$ will work---that would be the universal quantifier, not the existential quantifier. Oct 1 '14 at 15:49
• As others have pointed out, you're harbouring a misconception: the big-Oh notation doesn't care what the constants are, but you do! It's your job to prove that $f(n) \le c g(n)$. The larger $c$ is, the more likely this is to be true. Since the notation doesn't care about how large $c$ is (only that it doesn't change with $n$), you have the freedom to choose $c$ to be larger than $c=1$: use it. Oct 1 '14 at 15:50

## 2 Answers

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?

• Does $3n^2+O(n)$ mean $3n^2$ plus any function of $n$ whose asymptotic complexity is $O(n)$? Oct 1 '14 at 15:57
• @user6607 Yes, that is correct. Oct 1 '14 at 16:39

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

• What if you have a complicated function? How do you choose the constants? Oct 1 '14 at 16:11
• It's a case-by-case process. For each function, you need to analyze what happens with $f(x)$ and $g(x)$ (if you're trying to show $f = O(g)$) as $x$ gets large. Generally, when you're dealing with polynomials, such as in this case, it will turn out that you can bound it by some constant times the leading term. Oct 1 '14 at 16:16
• Correct me if I'm wrong, but in the general case, you should be able to take any $c \geq \lim_{n\to\infty} \frac{f(n)}{g(n)}$, right? To find $n_0$, you can plot $cf(n) - g(n)$ and look for a root. Oct 1 '14 at 16:42
• @WChargin you are indeed correct Oct 1 '14 at 16:42