Let a(n), b(n), g(n) be positive non-decreasing functions.

(a) Prove (using the definitions of and O) that if T (n) = a(n) + b(n), such that a(n)

(g(n)) and b(n) O(g(n)) then T(n) (g(n))

(b) Show (as a corollary) that if T (n) = (nlogb a) + O(nlogb a) then T (n) (nlogb a)