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 have to prove:

$O(x)+O(x^2)=O(x^2)$ for $x\to\infty$ where "O" is the Big-O-Notation

Specific functions are no problem for me, but I have some difficulties with this general form. But nevertheless I tried the following:

$O(x)$ means $|f_1(x)|\leq |C_1 \cdot g_1(x)|$ with $g_1(x)=x$, and $O(x^2)$ means $|f_2(x)|\leq |C_1 \cdot g_2(x)|$ with $g_2(x)=x^2$ So we get $C_1 x + C_2 x^2 \leq (C_1+C_2) x^2$, which is $O(x^2)$ with $C_3=C_1+C_2$.

Is this start ok or its a big fault? Any hint would be nice.

share|improve this question
1  
Assuming that all of this is as $x\to\infty$, it seems to me that you have the right idea. –  Gerry Myerson Jan 19 '12 at 21:44
    
Oh sorry, I forgot $x \to \infty$. I added it. Thanks –  ulead86 Jan 19 '12 at 21:50
1  
When you say "$C_1 x + C_2 x^2 \leq (C_1+C_2) x^2$" I would be happier if you added "if $x \ge 1$" –  Henry Jan 19 '12 at 21:55
1  
@Daniel: Your proof looks good to me also. Depending on the meticulousness of your professor, it may be necessary to explicitly state why you're allowed to write $x \leq x^2$. –  JavaMan Jan 19 '12 at 21:55
1  
As far as the last problem goes, just note that the minus sign is a distraction since you're taking absolute values. –  JavaMan Jan 19 '12 at 22:00
show 2 more comments

1 Answer 1

up vote 3 down vote accepted

$f(x) = O(g(x)) \space \leftrightarrow \exists c_1,x_0\in\mathbb{R}\space such\space that\space\forall x>x_0\space we \space have\space|f(x)| \leq C_1*|g(x)|$so if $f(x) = O(g(x))and\space for \space constant \space k\in\mathbb{R}\rightarrow O(k*f(x)) = O(g(x))$ and for $x>k$ so we have $O(g(x))\le O(x*f(x))$ so $O(g(x)) +O(x*O(g(x))) \le O(x*O(g(x)))+O(x*O(g(x))) (1)\space and\space O(x*O(g(x))) = O(2*x*O(g(x))) (2)$ from (1) and (2) : $O(g(x))+O(x*O(g(x))) = O(x*O(g(x)))$ and now put g(x) = x. the rest is prove of the following sentence and it's very easy you do it yourself as an exercise: $O(x*O(x)) = O(x^2)$

share|improve this answer
add comment

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.