CMPS42A Randomized Quicksort
C. Seshadhri · 66:01
Randomized algorithms “flip coins” to choose their behavior; this lecture shows that randomized quicksort is a simple coding fix (pick a uniform random pivot) whose expected running time is \(O(n \log n)\) on *every*...