Use Pseudo Code for #2 and Master Theroem for #5!!

Questions 1. Let T(n) be a running time function defined recursively as 0, T(n) -1, n=0 n-1 3T (n 1)- 2T(n-2), n> 1 a. Find a non-recursive formula for T(n) b. Prove by induction that your answer in part (a) is correct. c. Find a tight bound for T(n) 2. Let C(n) 13 2333+ +n3 be the sum of the first n cubes. a. Write a recursive algorithm to compute C(n) b. What is the recurrence relation for your algorithm? C. What is the time complexity of the algorithm you developed? 3. Consider the following algorithm Algorithm XYZ(r,q, n) Ir,q, n are positive integers 1. ifn - 1 then return r 2. else 3. ifn is odd then return XYZ(r.q,n -1) + (n - 1)q 4. else return XYZ(r, q, n-1) - (n 1)q a. b. C. What does the algorithm compute? What is the recurrence relation for the algorithm? What is the time complexity of the algorithm (solve the recurrence in part b). 4. Consider the following algorithm Algorithm XYZ(n) In is positive integers 1. ifn - 0 or1 then return 1 2. else for i 2 to n 5, tempb b+b+ a a temp 6. 8