Question 2 (8 marks) (From the DPU textbook, Exercise 2.5) Using the Master theorem or recursion tree methods, solve the following recurence relations and give bound for each of them a) T(n) 9T(n/3) +3n2 12n - 4, where n 21 b) T(n)-T(n-1) + n", where n > 1 and c > 0 c) T(n) = T(Vn) + 1, where n > b and T(b) = 2. Question 3: 10 marks) Suppose we have a subroutine merge2 to merge two sorted arrays in linear time (kn The purpose is to design a divide and conquer algorithm (Alg2) to merge k sorted arrays using merge2 recursively. a) Write a pseudocode for Alg2. (Hint: Assume that the input is given in a (k x n) rray with the rows and columns sorted in ascending order) b) Write the running time of Alg2 as a recurence relation. T(k)-? c) Construct a recursion tree with log k levels and (kn) work per level to represent the d) Since k is a constant, is Alg2 asymptotically faster than an algorithm with running time recurance relation obtained in part (b) (n log n)? why