Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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$. –  Arthur Fischer 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

1 Answer 1

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.