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, ti(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 is a non-negative integer. Include any necessary base cases in your recurrence relation. Hint: When n = 24, each of the recursive calls in a given instance of recursiveMethod is on a subproblem of the same size. Hint: The equation ha- j - i +1 may be helpful in expressing the problem size in terms of the parameters i and j. public void myMethod ( int DA ) { int n = A.length; recursiveMethod(A, 0, n-1); 1 2 3 } 5 6 public void recursiveMethod (int DA int i, int j ) { int mid= (i+j)/2 7 8 9 10 if (i max) max - Am if (A[m] > max) max = A[m]; } 16 17 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 (n) using the substitution method (iteration method). Show your steps. (c) Prove the correctness of your closed-form expression for 4 (n) (derived In Question th) for the case n = 24, where r e Z, using a proof by induction (d) Give a simple and concise function g(n) such that 4(n) (g(n)). Hint: "Simple and concise means that g(n) should have no constants and only a single term. z = {0} = {0,1,2,3,...) denotes the set of non-negative integers. (e) Prove that the closed-form expression for t; (na) you derived in Question Ibis (g(n)) using limits, where g(n) is the expression you obtained in Question 18 (O) Explain why the Master Theorem can or cannot be applied to the recurrence relation 4(). 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? 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, ti(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 is a non-negative integer. Include any necessary base cases in your recurrence relation. Hint: When n = 24, each of the recursive calls in a given instance of recursiveMethod is on a subproblem of the same size. Hint: The equation ha- j - i +1 may be helpful in expressing the problem size in terms of the parameters i and j. public void myMethod ( int DA ) { int n = A.length; recursiveMethod(A, 0, n-1); 1 2 3 } 5 6 public void recursiveMethod (int DA int i, int j ) { int mid= (i+j)/2 7 8 9 10 if (i max) max - Am if (A[m] > max) max = A[m]; } 16 17 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 (n) using the substitution method (iteration method). Show your steps. (c) Prove the correctness of your closed-form expression for 4 (n) (derived In Question th) for the case n = 24, where r e Z, using a proof by induction (d) Give a simple and concise function g(n) such that 4(n) (g(n)). Hint: "Simple and concise means that g(n) should have no constants and only a single term. z = {0} = {0,1,2,3,...) denotes the set of non-negative integers. (e) Prove that the closed-form expression for t; (na) you derived in Question Ibis (g(n)) using limits, where g(n) is the expression you obtained in Question 18 (O) Explain why the Master Theorem can or cannot be applied to the recurrence relation 4(). 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