Exercise $4.$ Divide and Conquer

We all know how to use a simple loop to find the maximum of n elements. But we decide to try the following recursive algorithm RecursiveMaximum instead:

recursively compute the maximum of the first half of the numbers

recursively compute the maximum of the second half of the numbers

return the larger of the two maxima

a$)$ Explain why RecursiveMaximum is divide$-$and$-$conquer, whereas MovePancakes was not.

Note that algorithm can be implemented in two ways. The first way is to make copies of the two halves of the array, and pass them to the recursive calls.

b$)$ Show detailed pseudocode for this algorithm; don't forget the base case$($s$).$

c$)$ Give the recurrence equation for your algorithm. If we've seen the same recurrence equation inclass before, state the solution. Otherwise, solve it by iterative substitution

The second approach is to keep all numbers in place and pass the indices of the subarrays to the recursive calls,

d$)$ Show detailed pseudocode for this algorithm; don't forget the base case$($s$).$

e$)$ Give the recurrence equation for your algorithm. If we've seen the same recurrence equation inclass before, state the solution. Otherwise, solve it by iterative substitution.

f$)$ Explain why $O(n)$ is the best running time that is possible for this algorithm, aka lower bound. Was it a good idea to try applying the divide$-$and$-$conquer approach to maximim?