2
$\begingroup$

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?

  • 1
    That, and possibly refer to said [definitions](http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations).2011-11-22

1 Answers 1

3

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?