Advanced Linear-Time Selection Algorithms

Key Insight

The general selection problem, which aims to find the 'i'th smallest element, can be solved in expected linear time using the `RANDOMIZED-SELECT` algorithm. This algorithm is structured like quicksort but critically recurses on only one side of the partition. It employs the `RANDOMIZED-PARTITION` procedure to select a pivot. While its worst-case running time is Theta(n^2) (e.g., if partitioning consistently yields the largest remaining element), its randomized nature ensures an expected linear running time of Theta(n) across all inputs, assuming distinct elements.

For a guaranteed worst-case linear time solution, the `SELECT` algorithm is used. This deterministic algorithm ensures a 'good split' by carefully choosing a pivot element. It first divides the 'n' elements into 'floor(n/5)' groups of 5, plus a remainder group. Then, it finds the median of each of these groups by insertion sorting them. The algorithm then recursively calls `SELECT` to find the median of these medians (the 'median-of-medians'), which serves as the partitioning pivot 'x'.

By using the median-of-medians 'x' as the pivot, `SELECT` guarantees that a significant fraction of elements are smaller than 'x' and a significant fraction are larger. Specifically, at least '3n/10 - 6' elements are guaranteed to be less than 'x' and '3n/10 - 6' elements greater than 'x'. This ensures that the recursive call in the worst case is made on a subarray of size at most '7n/10 + 6'. This leads to a recurrence relation 'T(n) <= T(ceil(n/5)) + T(7n/10 + 6) + O(n)', which, by substitution, proves a worst-case running time of O(n). These selection algorithms are not comparison sorts, allowing them to bypass the Omega(n log n) lower bound applicable to sorting.