Question 1.

a) Write a recursive Java function, void max( int[] A, int lo, int hi ), that finds the maximum value among the array elements A[lo], A[lo+1], . . . , A[hi], using the tournament method. (That is, find the maximums in two halves of the array and then compare them.)

b) This function can be used to find the max of an N-element array by calling max(A, 0, N-1). Write a recurrence relation for the run time, T(N ), of the function.

c) Use the Master Theorem to find T (N ). (Explain your reasoning. You shouldn't be surprised by the answer!)

Question 2.

Suppose that a recursive algorithm divides a problem of size n into 4 problems of size n/2. The amount of extra work that is done to split the problem into parts and to combine the results from processing the parts is Θ(n2). Write a recurrence relation for the run time of the algorithm and use the Master Theorem to find the run time. How does the answer change if the extra work has run time Θ(n³/2)?