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 am a total beginner with the big O and big theta notation. How would I prove the following?

If $f(n) \in O(g(n))$, then $f(n)+g(n) \in \Theta (g(n))$.

I am not sure how to go from the definition of $f(n) \in O(g(n))$. What's confusing me is how to get to $(f+g)(n)$? Can someone please put me in the right direction?

share|improve this question
1  
Unfold the definition of the premise and derive from that the constant(s) you need for the consequent. –  Raphael Nov 22 '11 at 18:37
1  
That, and possibly refer to said definitions. –  Did Nov 22 '11 at 19:00
add comment

1 Answer

You can add inequalities together. So if you have $a\le b$ and $c\le d$ then you get $a+c\le b+d$; in addition you can add them together with equalities so that if e.g. $e=f$ then $a+e\le b+f$, etc.

If you have that $f(n)\le Cg(n)$ for $n\ge N$ and $g(n)=1g(n)$, then what happens when you add these two together? Now presumably $f(n)\ge0$ so what happens if you add that to the latter afore-mentioned equation again?

share|improve this answer
    
thank you everyone –  mitsuki C Nov 22 '11 at 19:27
1  
@mitsukiC, if that answer satisfies you, then accept it. –  lhf Dec 22 '11 at 22:10
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.