Given n2k distinct numbers a1 a2 an and we wish to select k

Given n=2k distinct numbers, a_1, a_2, ...a_n and we wish to select k numbers and put them in an array B[l], B[2], ..., B[k] such that B[1]

Solution

Algorithm MinMax (A[0..n 1], minval, maxval) where

Algorithm MinMax (A[l..r], minval, maxval)

if r = l

minval A[l]; maxval A[l]

else if r l = 1

if A[l] A[r]

minval A[l]; maxval A[r]

else minval A[r]; maxval A[l]

else //r l > 1

MinMax(A[l..(l + r)/2

], minval, maxval)

MinMax(A[(l + r)/2

+ 1..r], minval2, maxval2 )

if minval2 < minval

minval minval2

if maxval2 > maxval

maxval maxval2

  Assuming for simplicity that n = 2k, we obtain the following recurrence for the number of element comparisons C(n):

C(n)=2C(n/2) + 2 for n > 2, C(2) = 1, C(1) = 0.

Solving it by backward substitutions for n = 2k, k 1, yields the following:

C(2k)=2C(2k1)+2

           = 2[2C(2k2) + 2] + 2 = 22C(2k2)+22 + 2

           = 22[2C(2k3) + 2] + 22 +2=23C(2k3)+23 + 22 + 2

           = ......

           = 2iC(2ki)+2i + 2i1 + ... + 2

             = ....

             = 2k1C(2) + 2k1 + ... +2=2k1 + 2k 2

             = 32n 2.

                                                        This algorithm makes about 25% fewer comparisons–1.5n compared to 2n–than the brute-force algorithm. (Note that if we didn’t stop recursive calls when n = 2, we would’ve lost this gain.) In fact, the algorithm is 5 optimal in terms of the number of comparisons made. As a practical matter, however,a nonrecursive scan of a given array that maintains the minimum and maximum values seen so far and updates them not for each element but for a pair of two consecutive elements makes the same number of comparisons as the divide-and-conquer algorithm but doesn’t have the recursion’s overhead.