Question :
Suppose that, in a divide and conquer algorithm, we divide an instance of size n of a problem into 16 sub instances of size n/4 and the dividing takes O(1) time (you may ignore this step). Then we combine the results which takes n2 operations.
Assume the next step the algorithm does is to sort the combined results. We use Insertion sort to sort the elements.
a. What is the recurrence equation for the running time, T(n)?
b. Solve for T(n).
c. If the algorithm used Quicksort instead (which has a complexity of theta (n log n)), then what is the running T(n) of the algorithm? Will there be an improvement in the performance? Explain your answer.