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)?

Answer 1

The lower bound for a group size of 7 is 8, the upper bound is +8.

The recurrence relation is T(n) = T(n/7) + T(5n/7) + O(n).

The worst-case time complexity is O(n).

Step-by-step explanation:

The lower bound for the number of elements that are guaranteed to be larger than the median of medians when using a group size of 7 is 8.

This is because the median of the medians will be the middle element of the upper half, and since there are 7 elements in the upper half, there will be at least 4 elements larger than the median.

The upper bound for the number of elements on either side of the median of medians after the partition when using a group size of 7 is + 8.

This is because there will be at most 7 elements on either side of the median of medians in the partition.

The recurrence relation of the time complexity of the algorithm, assuming a group size of 7, is T(n) = T(n/7) + T(5n/7) + O(n), where T(n) represents the time complexity of sorting a list of size n using the linear time selection algorithm.

The worst-case time complexity of the algorithm, assuming a group size of 7, is O(n), where n is the size of the input list.