Given An Array S S 1 S 2 S N And N 2dfor Some D 1 We Want To Findthe Minimum And

/in /by

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.

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…