The following divide-and-conquer algorithm is proposed for finding the

Chapter 7, Problem 7.40

(choose chapter or problem)

The following divide-and-conquer algorithm is proposed for finding the simultaneousmaximum and minimum: If there is one item, it is the maximum and minimum,and if there are two items, then compare them and in one comparison you can findthe maximum and minimum. Otherwise, split the input into two halves, dividedas evenly as possibly (if N is odd, one of the two halves will have one more elementthan the other). Recursively find the maximum and minimum of each half, andthen in two additional comparisons produce the maximum and minimum for theentire problem.a. Suppose N is a power of 2. What is the exact number of comparisons used bythis algorithm?b. Suppose N is of the form 3 2k. What is the exact number of comparisons usedby this algorithm?c. Modify the algorithm as follows: When N is even, but not divisible by four, splitthe input into sizes of N/2 1 and N/2 + 1. What is the exact number ofcomparisons used by this algorithm?