Let A[1..n] be an array of distinct numbers, and assume that the number of elements n 2 is a power of 2 (that is, 2, 4, 8, 16, ...).

(a) Give a divide-and-conquer algorithm that finds the second largest element in A (the element in A with exactly n2 elements smaller than it) by performing no more than 3n/2 2 comparisons. Analyze the number of comparisons performed by your algorithm by giving a recurrence relation and solving it. (Hint. Divide the array in two halves, find the largest and the second largest elements in each half, and then ...)