Consider the algorithm shown below which, given two positive integers i and n, a
ID: 3848208 • Letter: C
Question
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);
}
Give a recurrence equation (i.e., T(n)) for this algorithm
Explanation / Answer
Let us first put the line numbers to the algorithm, for the ease of explanation.
1. max(i, n, A):
2. if (n == 1)
3. return(A[i]);
4. else { m1 = max(i, floor(n/2), A);
5. m2 = max(i + floor(n/2), ceiling(n/2), A);
6. if (m1 < m2) return(m2);
7. else return(m1);
8. }
Recurrence equation for the above algorithm can be deduced as follows:
T(n) = T(n/2) [for line 4] + T(n/2) [for line 5] + c [constant time for lines 6 and 7] = 2T(n/2) + c. (if, n>1)
= 1 (if, n=1)