Question

Prove the additivity of big O notation:

f, g and h are functions of input size n. Prove that if  $f \in \mathbb{O}(h)$ and $g \in \mathbb{O}(h)$, then $f+g \in \mathbb{O}(h)$

Answer 1

Your question text is not very clear and hence, I am providing the proof for additivity of big O notation.

Let f(n) = O(h(n)) and g(n) = O(h(n))

Since f(n) = O(h(n)), this implies that

0 <= f(n) <= c1 * h(n) where c1 is a positive constant ---------> 1

Since g(n) = O(h(n)), this implies that

0 <= g(n) <= c2 * h(n) where c2 is a positive constant ---------> 2

Adding 1 and 2, we get

0 <= f(n) + g(n) <= (c1 + c2) * h(n) where c1 + c2 is a positive constant

Hence, f(n) + g(n) = O(h(n))