Consider the algorithm shown below which, given two positive integers i and n, and an array A, returns the element in A that has the maximum value. Initially, this algorithm would be called as max(1, length(A), A) in order to find the maximum value in the entire array A (assuming 1-based indexing).

max(i, n, A):

if (n == 1)

return(A[i]);

else

{

m1 = max(i, floor(n/2), A);

m2 = max(i + floor(n/2), ceiling(n/2),A);

if (m1 < m2)

return(m2);

else return(m1);

}

1. Solve the recurrence equation using the substitution method.

2. Find () for T(n) using the Master Method