2. The following algorithm is a divide-and-conquer algorithm for finding the maximum value in array A[1..n].

Question

Function maximum(x,y)

{ return maximum in A[x..y]}

1.                 if y - x £ 1 then return (max(A[x],A[y]))

2.                 else

3.                 max1 <--- maximum(x, [(x + y) / 2] )

4.                 max2 <--- maximum( [(x + y) / 2] + 1 , y)

5.                 return(max(max1, max2)   

Give a recurrence equation for the worst-case number of comparisons used by maximum (1, n), and solve this recurrence equation, (you may assume that n is a power of 2)

Answer 1

The recurrent equation should be something like this:

R(n) = { 1 when n <= 2, 1 + 2*R(n/2) when n > 2 }

Can you solve this equation yourself?