Skip to content
All tags

#randomized-algorithms

2 posts
learning deep-dive Reading Stanford CS161

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

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
learning deep-dive Reading Stanford CS161

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

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