Given an array s =(s[1], s[2], . . . , s[n]), and n = 2^d for some d = 1. We want to find the minimum and maximum values in s. We do this by comparing elements of s.
(a) The "obvious" algorithm makes 2n - 2 comparisons. Explain.
(b) Can we do it better? Carefully specify a more efficient divide-and-conquer algorithm.
(c) Let T(n) = the number of comparisons your algorithm makes. Write a recurrencerelation for T(n).
(d) Show that your recurrence relation has as its solution T(n) = 3n/2 - 2.