alt Hacker News+1. My favourite bit is when pivots are chosen randomly in quicksort, we get linearithmic expected complexity. The CLRS proof using indicator random vars was a oh-shit moment.
Replies
tmoertel • yesterday at 3:48 PM
Similarly, quickselect with random pivots runs in expected linear time.
For a proof of this, see https://github.com/tmoertel/practice/blob/master/dailycoding...
Btw, you can make quicksort deterministically O(n log n) if you pick the pivot point with linear median search algorithm. It's impressive how randomness lets you pick a balanced pivot, but even more impressive that you could do the same without randomness.