proving a "big-oh" summation?

Question

If f(n) is O(g(n)) and d(n) is O(h(n)), how can I prove that the summation f(n) + d(n) is O(g(n) + h(n))? It is obvious that this is true, but how do you prove it?

Answer 1

f(n)∈O(g(n)) ⇔ [n→∞]lim sup f(n)/g(n) < ∞

Also note that for any functions f and g, [n→∞]lim sup (f(n)+g(n)) ≤ [n→∞]lim sup f(n) + [n→∞]lim sup g(n).

So let f(n)∈O(g(n)) and d(n)∈O(h(n)), then [n→∞]lim sup f(n)/g(n) = L₁ < ∞ and [n→∞]lim sup d(n)/h(n) = L₂ < ∞. Then we have:

[n→∞]lim sup (f(n) + d(n))/(g(n) + h(n))
= [n→∞]lim sup (f(n)/(g(n) + h(n)) + d(n)/(g(n) + h(n)))
≤ [n→∞]lim sup (f(n)/g(n) + d(n)/h(n))
≤ [n→∞]lim sup f(n)/g(n) + [n→∞]lim sup d(n)/h(n)
= L₁ + L₂ < ∞

So f(n)+d(n) ∈ O(g(n)+h(n)). Which was to be demonstrated.