Problem 4 (5 points). Use the master theorem to find the asymptotic tight bounds for the running times of the algorithms characterized by the following recurrence relations. For each relation, indicate the case of the master theorem you used to find your solution and explain the reason for which you have used that case. (a) T(n) = 64T (3) +- (b) T(n) = 167(%) + 5mi (e) T(n) = TC + Problem 5 (4 points). We consider the merge sort algorithm that uses a divide-and-conquer design strategy. The running time of a merge sort algorithm is given below: T'lo= {r+- if n=2 if n=2K, K>1 Prove that the expression giving the complexity of the merge sort algorithm with which you are already familiar is also a solution to the above recurrence. Hint: use mathematical induction