In this problem, we will explore the idea of using a divide-and-conquer approach to finding the maximum value in an array of n integers.

Inputs:

an array A of integers

an integer L (the index of the leftmost array element to be considered)

an integer R (the index of the rightmost array element to be considered)

FindMax (A,L,R): if (L == R) return A[L] else y + FindMax(A,L,x) z + FindMax (A,x+1,R) if (y > z) return y else return z We can find the maximum value in an array A of size n by calling FindMax (A,1,n). (a) Write a recurrence relation to express T(n), the running time of this algorithm for an input of size n. (b) Use the Master Theorem to solve this recurrence. (c) How does this compare, in terms of asymptotic running time, to a simple algo- rithm that just steps through each element of the array one at a time and uses a variable to remember the largest value seen so far