Asymptotic Notation Properties. (20 points) Let f (n) and g(n) be asymptotically non-negative functions. Using the definitions of asymptotic notation: (a) (5 points) Prove that if f (n) = o(g(n)) and g(n) = o(h(n)) then f (n) = o(h(n)). (b) (5 points) Prove that if f1(n) = O(g1(n)) and f2(n) = O(g2(n)) then f1(n) + f2(n) = O(g1(n) + g2(n)). (c) (5 points) Prove that if f (n) = O(n) + O(n2) + O(n3) then f (n) = O(n3). (d) (5 points) Disprove that if f (n) = O(g(n)) and g(n) = (h(n)) then f (n) = (h(n)). To do this, you need to provide a counterexample by showing a specific f (n), g(n), h(n) that do not satisfy the above statement.

(algorthim )