Search code examples
complexity-theory

Proof of closure of asymptotically bounded functions under addition

I would like to prove this statement:

If f(n) is Theta(h(n)) and g(n) = O((h(n)) then f(n) + g(n) is O(h(n)).

All functions are assumed to be non-negative and monotonically non-decreasing.

My attempted proof explains that if f(n) and g(n) are O(h(n)) then there exists:

positive constants n0, c0 such that f(n) <= c0*h(n) for all n >= n0

positive constants n1, c1 such that f(n) <= c1*h(n) for all n >= n1

Therefore it can be deduced that g(n) + f(n) <= (c1 + c0) * h(n) for all n >= max(n1, n0) meaning that g(n) + f(n) is O(h(n))

Is this correct? Is there a more rigourous proof ... for example, by contradiction?

Solution

  • Your proof is correct and rigorous. It is direct and constructive proof in that you not only show that suitable c and n0 exist, but you say how to calculate them from the assumptions. No other simpler methods of proof come to mind here.