Consider the following divide-and-conquer algorithm that assumes a global array A of integers:

Before running the algorithm, we ask the user to enter n integers that we store in the array A. Then we run WHATDOIDO(0,n-1).

a) State the recurrence for T(n) that captures the running time of the algorithm as closely as possible.

b) Use either the unrolling the recurrence (telescoping) or mathematical induction technique to find a tight upper bound on T(n).

c) What does the algorithm do? Specify what the three returned values represent.