Show that $f(x) = x^2 + 5x + 9$ is $O(x^2)$.

Question

This involved the big O notation. I can understand a bit of big O notation but answering this question to me is difficult. None of the examples I have come across are working out for me. Can someone tell me what is the answer, and how do I answer this? Thank you!

Start with the definition of $f(x) = \mathcal{O}(x^2)$ – Winther Sep 15 '14 at 14:06 — Winther, Sep 15 '14 at 14:06

score 0 · Answer 1 · answered Sep 15 '14 at 14:05

0

For $x>1, f(x)=x^2(1+5x^{-1}+9x^{-2})\leq x^2(1+5+9)=15x^2$. So, by the definition of big-$O$, $f(x)$ is $O(x^2)$

answered Sep 15 '14 at 14:05

Matt Gallagher

471

score 0 · Answer 2 · answered Sep 15 '14 at 14:30

As a more general rule:

If you have a polynomial $$ f(x)= a_n x^n+\ldots a_1x^1 +a_0$$ with $a_n>0$ and you consider its asymptotic behavior for $x\to\infty$, you divide by $x^{-n}$ and get:

$$ x^{-n} f(x)= a_n +\ldots a_1x^{-n+1} +a_0 x^{-n}$$

For $x\to \infty$ this goes to $a_n$, so $f(x)$ is $O(x^n)$.

Show that $f(x) = x^2 + 5x + 9$ is $O(x^2)$.

2 Answers2