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?

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