Lesson 3

It can be shown that the expected running time of Randomized QuickSelect is \(O(n)\). Designing a deterministic algorithm having worst-case running time \(O(n)\) is not an easy task. The median-of-medians algorithm, due to Blum, Floyd, Pratt, Rivest, and Tarjan (four of them are Turing Award winners!), achieves this goal.