1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ "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$. $\endgroup$ Oct 1 '14 at 15:43
  • $\begingroup$ 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. $\endgroup$
    – Lee Mosher
    Oct 1 '14 at 15:49
  • $\begingroup$ 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. $\endgroup$
    – Erick Wong
    Oct 1 '14 at 15:50
1
$\begingroup$

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?

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

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

$\endgroup$
4
  • $\begingroup$ What if you have a complicated function? How do you choose the constants? $\endgroup$
    – user6607
    Oct 1 '14 at 16:11
  • $\begingroup$ 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. $\endgroup$ Oct 1 '14 at 16:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – wchargin
    Oct 1 '14 at 16:42
  • $\begingroup$ @WChargin you are indeed correct $\endgroup$ Oct 1 '14 at 16:42

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.