Suppose $f(n)$ is $O(g(n))$ and $d(n)$ is $O(e(n))$. How do i use Big O to show that $f (n)$ + $d(n)$ is $O(g(n) + e(n))$?

Question

Suppose $f(n)$ is $O(g(n))$ and $d(n)$ is $O(e(n))$. How do I use Big O to show that $f(n) + d(n)$ is $O(g(n) + e(n))$?

Answer 1

In generally this is false (if we follow the definition given at Wikipedia). For example with $f(n)=g(n)=d(n)=-e(n)=n$ We have $f(n)=O(g(n))$ and $d(n)=O(e(n))$ but not $2n=f(n)+d(n)=O(g(n)+e(n))=O(0)$.

However, if we assume $g(n)$ and $e(n)$ are non-negative, then the claim follows: We are given that $|f(n)|\le c_1g(n)$ for all $n>N_1$ and $|d(n)|\le c_2e(n)$ for all $n>N_2$. Then $$|f(n)+d(n)|\le |f(n)|+|d(n)|\le c_1g(n)+c_2 e(n)\le\max\{c_1,c_2\}(g(n)+e(n))$$ for all $n>\max\{N_1,N_2\}$.