Selection in worst-case linear time in Design and analysis of algorithms free pdf
To analyze the running time of SELECT, we first determine a lower bound on the number of elements that are greater than the partitioning element x. Figure is helpful in visualizing this bookkeeping. At least half of the medians found in step 2 are greater than the median-of-medians x. Thus, at least half of the ⌈n/5⌉ groups contribute 3 elements that are greater than x, except for the one group that has fewer than 5 elements if 5 does not divide n exactly, and the one group containing x itself.