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              ---->    ∞ 
  • 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
    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
    @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