# Problem with this Big $O$ proof

I've been reading the wikipedia article about $Big O$ notation:

and i'm not sure about the second step in wich $6x^4 + |2x^3|+5$ turns into $6x^4 + 2x^4+5x^4$. How is it that the $x^4$ appears in there?

-
It's just that for all $x \geq x_0 = 1$ we have that $| 2x^3 | \leq 2 x^4$ and $5 \leq 5 x^4$. – arjafi Jun 26 '12 at 7:33
@mayhem:$6x^4 + |2x^3|+5 \leq$ $6x^4 + 2x^4+5x^4$(not equal) – Aang Jun 26 '12 at 7:38

The point is that if $x>1$, then $x^4>|x^3|$ and $x^4>1$, so $|2x^3|\le 2x^4$ and $5\le 5x^4$, and therefore

$$6x^4+|2x^3|+5\le 6x^4+2x^4+5x^4\;.$$

The reason for pushing all of the terms up to multiples of $x^4$ is to allow factoring out $x^4$ in the next step: $6x^4+2x^4+5x^4=13x^4=13|x^4|$. This shows that for all $x>1$, $|6x^4-2x^3+5|\le 13|x^4|$. In other words, there is a number $x_0$ and a positive number $M$ such that

$$|6x^4-2x^3+5|\le M|x^4|$$

whenever $x>x_0$: specifically, $x_0=1$ and $M=13$ will work.

-
So basically what you are saying is that i could put for example: $6x^5+2x^5+5x^5$ if i would need to, and it would still correct because the inequality $6x^4+|2x^3|+5\le 6x^5+2x^5+5x^5\$ in my example persists. – mayhem Jun 26 '12 at 7:50
@mayhem: Yes, assuming that $2^x5$ is a typo for $2x^5$, but then you’d only be showing that the original polynomial is $O(x^5)$, not $O(x^4)$. – Brian M. Scott Jun 26 '12 at 7:52
Could i think of this proof as a general one to apply when i'm ask to prove some polynomial of this type? in order to make thins easy – mayhem Jun 26 '12 at 7:59
@mayhem: You can do better than that: you can use this example as a model to prove the general theorem that if $p(x)$ is a polynomial of degree $n$, then $p(x)$ is $O(x^n)$. – Brian M. Scott Jun 26 '12 at 8:02