Branch: : Aeronautical Engineering
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.
- Selection in expected linear time in Design and analysis of algorithmsfree notes
- Randomized algorithms in Design and analysis of algorithms free pdf
- Analyzing divide-and-conquer algorithms in Design and analysis of algorithms free pdf
- Analysis of insertion sort in Design and analysis of algorithms free pdf notes
- Introduction to Algorithms Design and analysis of algorithms free pdf