Big O notation proof statement

Question

So here it is:
If $f(n) = O(g(n))$ and $d(n) = Ο(h(n))$, then I have to prove the following: $$f(n) + d(n) = Ο(g(n)+ h(n))$$

Any ideas?

Answer 1

You know that $\exists k \in \mathbb{N}, c \in \mathbb{R}$ such that $\forall n \geq k, f(n) \leq c*g(n)$. Similarly there $\exists k' \in \mathbb{N}, c' \in \mathbb{R}$ such that $\forall n \geq k', d(n) \leq c'*h(n)$. Now notice simply that for all $n \geq \max(k,k')$:

$$ f(n) + d(n) \leq cg(n)+c'h(n) \leq \max(c,c')(g(n)+h(n))\implies f(n)+d(n) = \mathcal{O}(g(n)+h(n)) $$

That was a little terse, so to quickly just elaborate, I get the inequalities from the top by noting that $f(n) = \mathcal{O}(g(n))$ and $d(n) = \mathcal{O}(h(n))$, and then I can use those to see that I satisfy the definition of big oh for $f(n) + d(n)$.