d. (4 pts) Fill in the asymptotic complexity (not the exact solution) of the work represented by the following summations for an input of size n. Write complexities in simplest form. ) (1) 2' = 01 (3) Z(64) = 01_ (2) (Si +5) = 01 - (4) I"3n =01_ logn ) ) e. (5 points) Consider the recurrence T(n) = 4T(n/2) +n , T(2) = 8. and a proposed closed-form solution T(n) = n + 2n Suppose we want to prove by induction that the closed-form solution is correct. Fill in the blanks to complete the following statements about an inductive proof: i) (1 point) Let n = 2. The proposed closed form yields T(2) = __ = 8, which matches the value given for the base case. Thus the base case is valid. ii) (2 points) By the inductive hypothesis we assume that T(n/2) = iii) (2 points) Does the proof go through? If so, mark 'YES'. If not, mark 'NO' and explain where the proof breaks down. YES _NO Explanation