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\h(n)`

from which it follows that


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