0
$\begingroup$

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

http://en.wikipedia.org/wiki/Big_O_notation#Example,

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?

  • 0
    @mayhem:$6x^4 + |2x^3|+5 \leq$ $6x^4 + 2x^4+5x^4$(not equal)2012-06-26

1 Answers 1

2

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.

  • 0
    @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)$.2012-06-26