Question

Show that if f(n) is O(g(n)) and d(n) is O(h(n)) then f(n) + d(n) is O(g(n) + h(n)).

Answer 1

$f(n)\in\mathcal O(g(n))$ is to say

$|f(n)|\le M_1|g(n)|$

for all $n$ beyond some fixed $n_1$.

Similarly, $d(n)\in\mathcal O(h(n))$ is to say

$|d(n)|\le M_2|h(n)|$

for all $n\ge n_2$.

From this we can gather that

$|f(n)+d(n)|\le|f(n)|+|d(n)|\le M_1|g(n)|+M_2|h(n)|\le M(|g(n)|+|h(n)|)$

where $M$ is the larger of the two values $M_1$ and $M_2$, or $M=\max\{M_1,M_2\}$. Then the last term is bounded above by

$M(|g(n)|+|h(n)|)\le2M\max\{|g(n)|,|h(n)|\}$

from which it follows that

$f(n)+d(n)\in\mathcal O(\max\{g(n),h(n)\})$