0
$\begingroup$

Prove that if $f(n) \in \mathcal{O}(h(n))$ and $g(n) \in \mathcal{O}(h(n))$ then $f(n) + g(n) \in \mathcal{O}(h(n))$.

I know that $\mathcal{O}(g(n))=\{f\space | \space\exists c\in\mathbb{R}^{+},\exists n_{0} \in \mathbb{N},\forall n\geq n_{0} : f(n)\leq c\cdot g(n)\}$

However, what do I do with this information to obtain the proof?

1 Answers 1

2

Hint: Let $f(n) for all $n>n_1$ and $g(n) for all $n>n_2$. That such $k_1, k_2, n_1, n_2$ exists is given in the problem. Now find a $k$ and an $N$ such that $f(n)+g(n) for all $n>N$. This proves that $f+g\in O(h)$.