Assignment 5 is intended to help students analyze the running time of recursive algorithms. You must show your steps and formulae used in your solutions to questions. Read each question carefully. You can assume that all recurrence relations are non-decreasing. You can omit floor and ceiling rounding in your expressions. 1. (a) Give a recurrence relation, (n), that expresses the number of times a value in the array A is accessed (read or write) in the worst case by a call to myMethod(A), where n denotes the length of A. Do not count the length operation on Line 2. To simplify your analysis, you can assume that n=2", where r is a non-negative integer. Include any necessary base cases in your recurrence relation. Hint: When n=2", each of the recursive calls in a given instance of recursiveMethod is on a subproblem of the same size. Hint: The equation n = j - i+1 may be helpful in expressing the problem size in terms of the parameters i and j. 1 public void myMethod (int OA) { 2. int n = A.length; 3 recursiveMethod(A, 0, n-1); 4. } 5 6 public void recursiveMethod (int DA, int i, int j ) { 7 int mid = (i+j)/2; 8 9 if (i max) max = A[m]; } 18 19 20 21 22 23 24 25 if (max > 1000) { recursiveMethod(A, i, mid); recursiveMethod(A, mid+1, j); } } } (b) Find a closed-form expression for your recurrence relation 6(n) using the substitution method (iteration method). Show your steps. (c) Prove the correctness of your closed-form expression for (n) (derived in Question IT) for the case n = 2-, where r e Z", using a proof by induction] (d) Give a simple and concise function gn) such that (7) e (g(n)). Hint: "Simple and concise means that should have no constants and only a single term. z = Z (0) = (0,1,2,3...) denotes the set of non-negitive integer (e) Prove that the closed-form expression for t(n) you derived in Question 16 is (g(n)) using limits, where g(n) is the expression you obtained in Question 10 (1) Explain why the Master Theorem can or cannot be applied to the recurrence relation 1:(n). What are the values for a, b, and f(n), which case of the theorem does this recurrence fall under, and what can we conclude