Skip to content
All tags

#randomized-algorithms

2 posts
learningdeep-diveReading Stanford CS161 Design and Analysis of Algorithms

Proving Randomized QuickSort's Expected Time | Stanford CS161 Lecture 5

Randomized QuickSort has O(n log n) expected time on every fixed input but Θ(n²) worst-case time. The valid proof does not substitute expected subproblem sizes into a recurrence; it computes the probability that each pair is compared.

#cs161#algorithms#stanford#quicksort#randomized-algorithms
learningdeep-diveReading Stanford CS161 Design and Analysis of Algorithms

Hashing, Collisions, and What Expected O(1) Actually Guarantees | Stanford CS161 Lecture 8

A universal hash family only needs to keep the collision probability of every distinct key pair at most 1/n; that makes the expected bucket size below 2, yielding expected O(1), not per-operation worst-case O(1).

#cs161#algorithms#stanford#hashing#randomized-algorithms