Given the following algorithm

A. Write a recurrence relation to express T(n), the running time of the algorithm for an input size n

B. Use the master theorem to solve the recurrence

C. How does this compare in terms of asymptotic running time to a simple algorithm 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?

Inputs: an array A of integers an integer I (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 LR y + FindMax (A,L,X) 2+ FindMax(A,x+1, R) if (y > 2) return y else return z We can find the maximum value in an array A of size n by calling FindMax (A,1,n)