Similarly, quickselect with random pivots runs in expected linear time.

For a proof of this, see https://github.com/tmoertel/practice/blob/master/dailycoding...