We have studied the linear time selection algorithm. In the algorithm we have studied, we used group

Fantastic news! We've Found the answer you've been seeking!

Question:

We have studied the linear time selection algorithm. In the algorithm we have studied, we used group size of 5. We proved that the number of elements that are guaranteed to be larger than the median of medians is lower bounded by 6. Similarly, the number of elements that are guaranteed to be smaller than the median of medians is also lower bounded by 6. Therefore, the number of elements on either side of the median of medians after the partition is upper bounded by + 6. Answer the following questions.

Suppose we use group size of 7. What is the corresponding lower bound? What is the corresponding upper-bound? What is the recurrence relation of the time complexity of the algorithm (in asymptotic notation)? What is the worst-case time complexity of the algorithm (in asymptotic notation)?

Suppose that we modify the quicksort algorithm in the following way. Instead of using the last element as the pivot element for partition, we apply the linear time selection algorithm to compute the median of the original array (i.e., the -th smallest element, where n is the total number of elements in the array), and use the median as the pivot element for partition in our revised quicksort. Let T_A(n) denote the worst-case time complexity of our revised quicksort algorithm (as described here).

Write down the recurrence relation for T_A(n). Also write down the asymptotic notation for T_A(n). You have to use the most accurate asymptotic notation.

Suppose that we modify the quicksort algorithm in a different way, as described in the following. Instead of using the last element as the pivot element for partition, we apply the linear time selection algorithm to compute the median of medians (using group size of 9) and use the computed median of medians as the pivot element for partition in our second revised quicksort. Let T_B(n) denote the worst-case time complexity of our second revised quicksort algorithm (as described here). Write down the recurrence relation for T_B(n).