Don’t forget that it takes linear time just to read the input! Basically, there’s a cool way to think about the progress the algorithm makes in terms of a simple coin-flipping experiment. It’s easy to solve this problem in O(n log n) time using sorting, but we can do better! This is a super-practical randomized algorithm, very much in the spirit of Quick Sort, that has linear expected running time.
Problem of computing the ith smallest element of an input array (e.g., the median). Prerequisite : Knowledge of partitioning array around random pivot.
