Problem1:

Prove that if f1(n) =O(g1(n)) and f2(n) =O(g2(n)) then f1(n) +f2(n) =O(g(n)) where g(n) = max(g1(n), g2(n)).  Assume all functions are non-negative.

Given,
f1(n) = O(g1(n)),
f2(n) = O(g2(n))

Let g'(n) = f1(n) + f2(n)

and, g'(n) and O(g(n))

By the definition of O of a function, if g'(n) =O(g(n)), then cg(n) >= g'(n) for n greater than some n' and a positive constant c.

Clearly, O(g'(n)) is O(f1(n) + f2(n))
Therefore, O(g'(n)) is O(g1(n)+g2(n))

Case1, if g1(n) = g2(n) then O(g'(n)) is O(2g1(n)); but by the definition of O, it should be trivially and without loss of generality, O(max(g1(n),(g2(n))).

Case2, we simply take O(max(g1(n), g2(n))) as O(g(n)) because at some point with certain values of n' and c, O(max(g1(n), g2(n))) will be true, by definition. Q.E.D