0

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?

mayhem
  • 113

1 Answers1

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.

Brian M. Scott
  • 616,228
  • 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 07: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 07: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 07: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 08:02