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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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
That, and possibly refer to said definitions. – Did Nov 22 '11 at 19:00

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

Your Answer


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.