4
$\begingroup$

For Big-O notation in mathematics,

How does $f(n) = 2n^2 + 3n + 1 = O(n^2)$?

Does it require any more information for the proof?

Edit:

c    ≥6       ≥3 * 3/4      ≥3 * 1/9          ---->    2
--------------------------------------------------------------
N     1          2             3              ---->    ∞
  • 1
    By definition $2n^2 + 3n + 1 = O(n^2)$ if and only if for some $n_0$ and $M$ we have $|2n^2 + 3n + 1| \leq M \cdot |n^2|$ for all $n > n_0$. So to prove the statement, simply provide such an $n_0$ and $M$.2011-09-14
  • 0
    You're essentiall talking about rates of growth. The statement means that |f(x)|2011-09-14
  • 0
    I'm not trying to copy you Thijs. I messed up typing my comment and slowed myself down a lot.2011-09-14
  • 0
    First, you have to agree on a definition. See [here](http://cstheory.stackexchange.com/questions/1718/which-definition-of-asymptotic-growth-rate-should-we-teach) for a discussion.2011-09-14

3 Answers 3

5

If $n\geq 3$, then $3n\leq n^2$ and $1\lt n^2$, so $|f(n)|\lt 2n^2 + n^2 + n^2 = 4n^2$

Hopefully, you can see how, with any polynomial, $p$, of degree $k$, $p(n)$ is $O(n^k)$.

  • 0
    Hopefully, indeed!2011-09-14
  • 0
    Along the same lines you can easily prove that any polynomial of degree $k$ is in $\cal{O}(n^l)$ for all $l \geq k$.2011-09-14
3

A simple proof here is noticing that $\lim_{n\to\infty}\frac{2n^2+3n+1}{n^2}=2$; this implies the result immediately (since $\text{}$$2<\infty$).

2

The formula in the question is actually a kind of abuse of notaion. Here is my favorite article about the big O notation:

http://en.wikipedia.org/wiki/Big_O_notation

which can also answer your questions.

  • 0
    Can you explain why it is an abuse of notation? If I want to express the question correctly without any abuse of notation, how do I do it?2011-09-14
  • 0
    @Srivatsan: it's abuse in the sense that $=O(2)$ on it's own does not have any actual meaning. It's supposed to be written $\ldots= O(2)\text{ as }x\to\infty$. I personally don't even use the $=$ in this context, I prefer to write out "$f$ is $O(2)$", or (though this is uncommon notation) $f\in O(2)_{\partial\mathbb{R}}$.2011-09-14
  • 0
    "uncommon"?! Using $\in$ is correct as $\cal{O}(.)$ is a *class* of functions. Using $=$ is just plain wrong and leads to confusion among beginners more often than not. You need $x \to \infty$ in either case, at least if more than one symbol is involved.2011-09-14
  • 0
    @Srivatsan: The questions are correct. It's a convention to use this kind of *abuse of notation* especially in numerical analysis. You can find the reason why I said it an abuse of notation in the link I gave in full details.`:-)`2011-09-14