2

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?

Srivatsan
  • 26,311
mitsuki C
  • 21

1 Answers1

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?

anon
  • 151,657