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
    Unfold the definition of the premise and derive from that the constant(s) you need for the consequent.2011-11-22
  • 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