3. 19] Suppose that, in a divide and conquer algorithm, we divide an instance of size...

 

Transcribed Image Text:

3. 19] 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 n operations. Assume the next step the algorithm does is to sort the combined results. We use Insertion sort to sort the elements. [Note: Basically there are 3 steps in the algorithm: recursively calling the sub-problems, combining and sorting.] a. [3] What is the recurrence equation for the running time, T(n)? b. [3] Solve for T(n). c. [3] If the algorithm used Quicksort instead (which has a complexity of O(nlogn)), then what is the running T(n) of the algorithm? Will there be an improvement in the performance? Explain your answer. 3. 19] 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 n operations. Assume the next step the algorithm does is to sort the combined results. We use Insertion sort to sort the elements. [Note: Basically there are 3 steps in the algorithm: recursively calling the sub-problems, combining and sorting.] a. [3] What is the recurrence equation for the running time, T(n)? b. [3] Solve for T(n). c. [3] If the algorithm used Quicksort instead (which has a complexity of O(nlogn)), then what is the running T(n) of the algorithm? Will there be an improvement in the performance? Explain your answer.