In class we showed an algorithm that finds the smallest and

In class, we showed an algorithm that finds the smallest and the largest of n numbers using 3n/2 - 2 comparisons when n is even, (a) Show how to find these two elements using 3n/2 - 3/2 comparisons when n is odd. (b) Assume that n = 2^k for some integer k greaterthanorequalto 1, design a divide-and-conquer algorithm to find both min and max elements with 3n/2 - 2 comparisons. Describe your algorithm first and then show why it takes 3n/2 - 2 comparisons.

Solution

Hi, I am giving you Algorithm for part 2.

b)
Divide and Conquer Algorithm:

Divide the array into two parts and compare the maximums and minimums of the the two parts to get the
maximum and the minimum of the the whole array.

MaxMin(array, array_size)
if array_size = 1
return element as both max and min
else if arry_size = 2
one comparison to determine max and min
return that pair
else /* array_size > 2 */
recur for max and min of left half
recur for max and min of right half
one comparison determines true max of the two candidates
one comparison determines true min of the two candidates
return the pair of max and min

Total number of comparisons:
let number of comparisons be T(n).
T(n) can be written as follows:

T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2
T(2) = 1
T(1) = 0
If n is a power of 2, then we can write T(n) as:
T(n) = 2T(n/2) + 2
After solving above recursion, we get
T(n) = 3/2n -2
Thus, the approach does 3/2n -2 comparisons if n is a power of 2.
And it does more than 3/2n -2 comparisons if n is not a power of 2.