7. Randomization: Skip Lists

What this lecture covers

The lecture answers how to build a randomized data structure, the skip list, that supports search, insert and delete in O(log n) time, and how to prove a much stronger guarantee than an expected-time bound: that the search cost is O(log n) "with high probability." Professor Devadas starts from a single sorted linked list, generalizes to multiple stacked sorted lists with progressively fewer elements, and shows how randomized promotion during insertion keeps the structure balanced without needing rebalancing operations.

This is the seventh lecture in MIT's Design and Analysis of Algorithms course, continuing the module on randomized algorithms and data structures. After watching, you should be able to describe the skip list's search and insert algorithms, explain why stacking sqrt(n)-spaced lists gives O(sqrt(n)) search while log n levels give O(log n), and follow the "with high probability" proof strategy that bounds the number of levels and the number of moves in a backward search using a union bound and Chernoff's bound.

Key ideas

• Skip list: a randomized data structure of stacked sorted linked lists, where the bottom list holds all n elements and each higher list holds a random subset, letting search "skip" over many elements at once.
• Search algorithm: starting at the top list, walk right until the next step would overshoot the target, then drop down a level and repeat, until the element is found or the search fails at the bottom list.
• Optimal spacing for two lists: with a fixed top list interspersed uniformly among n bottom elements, the search cost is minimized when the top list has sqrt(n) elements, giving O(sqrt(n)) total search cost.
• Generalizing to k lists: with k evenly spaced lists, the optimal search cost is k * (k-th root of n); setting k = log n gives search cost 2 log n, i.e. O(log n).
• Randomized insert: insert x into the bottom list at the right sorted position, then repeatedly flip a fair coin — on heads, promote x to the next level up (creating it if needed) and flip again; on tails, stop.
• "With high probability" (w.h.p.): a bound of the form c log n that holds with probability at least 1 - 1/n^alpha for some constant alpha > 0 related to c; a strictly stronger guarantee than an expectation, since it bounds how often the algorithm can be slow, not just its average cost.
• Warm-up lemma on levels: using a union bound over n insertions, the number of levels in an n-element skip list is O(log n) with high probability, because the probability that any single element is promoted more than c log n times is 1/n^(c-1).
• Backward search analysis: reading a successful search path backward from the found element, each step is either a left move (the element wasn't promoted at insertion, i.e. it got tails) or an up move (it was promoted, i.e. it got heads), each with probability 1/2, and the total number of moves equals the number of fair coin flips needed to get c log n heads.
• Chernoff bound: a probabilistic tool bounding how far a sum of independent coin flips can deviate from its expectation, used to show that the number of coin flips needed to reach c log n heads is itself O(log n) with high probability, completing the search-time proof.

Walkthrough

From sorted lists to a two-level skip list (4:07)

The lecture starts with the baseline: search in an unsorted linked list is O(n), and search in a single sorted linked list is still O(n) because there is no random access to support binary search. Adding a second, sparser sorted list on top (illustrated with New York subway express and local stops) lets a search walk right on the top list until it would overshoot, then drop to the bottom list — the seed idea of a skip list.

Optimizing the spacing of two lists (12:25)

The search algorithm is formalized: walk right in the top list until going further would overshoot, then walk down and continue in the bottom list. Treating the top list's size as a free parameter, the total cost is roughly (size of top list) + n / (size of top list), which is minimized when the top list has sqrt(n) elements evenly spaced, giving O(sqrt(n)) search cost.

Generalizing to log n levels (21:42)

Adding more evenly spaced lists reduces the cost further: with k lists, optimal spacing gives O(k * n^(1/k)) search cost. Setting k = log n levels yields 2 log n, i.e. O(log n) — but this analysis assumes a static, perfectly structured set of lists, which breaks down once insertions and deletions are allowed.

Randomized insertion by coin flips (33:12)

To insert an element, the lecture places it in its sorted position in the bottom list, then repeatedly flips a fair coin: heads promotes the element to the next level (creating a new list if necessary) and flips again, while tails stops the promotion. This keeps insertion simple but means the resulting structure's shape is random rather than perfectly regular, motivating a probabilistic rather than worst-case analysis. A special minus-infinity sentinel is used at the front of every level to simplify the search's edge cases.

Defining "with high probability" and the warm-up lemma (43:43)

The lecture defines a bound as holding "with high probability" when the failure probability is at most 1/n^alpha for a controllable constant alpha. It then proves a warm-up lemma: the number of levels in an n-element skip list is O(log n) with high probability. The proof bounds the probability that any single element is promoted more than c log n times by (1/2)^(c log n) = 1/n^c, then applies a union bound over all n inserted elements to get overall failure probability n * (1/n^c) = 1/n^(c-1).

Backward search and reducing to coin flips (54:59)

To bound the total number of moves in a search, the lecture analyzes a successful search backward from the found element: at each step, if the element was not promoted during insertion, the backward search made a left move (corresponding to a tails); if it was promoted, it made an up move (a heads). Since the search cannot make more up moves than there are levels, the total number of moves equals the number of fair coin flips needed to reach c log n heads — turning the search-time question into a question about coin flips.

Chernoff's bound and completing the proof (1:10:27)

The lecture introduces Chernoff's bound, which bounds the probability that a sum of independent coin flips deviates from its expectation by more than r, decaying exponentially in r^2/m. Applying Chernoff's bound (with an appropriately chosen constant d, such as d = 8c), the lecture argues that the number of coin flips needed to reach c log n heads is itself O(log n) with high probability. Combining this with the earlier bound on the number of levels (using a union of the two "with high probability" events) completes the proof that search in a skip list costs O(log n) with high probability.

Before you watch

• Watch the earlier randomization lecture introducing Monte Carlo and Las Vegas algorithms, since this lecture assumes familiarity with probabilistic analysis of algorithms.
• Be comfortable with basic probability (expectation, union bound) as background for the "with high probability" definition and proofs.
• Familiarity with balanced binary search trees is useful, since skip lists are presented as an alternative achieving similar O(log n) bounds without explicit rebalancing.

Check your understanding

1. Why does sorting a plain linked list not improve search from O(n), unlike sorting an array?
2. Why is sqrt(n) the optimal size for a second, sparser list stacked on top of an n-element sorted list?
3. In the randomized insert algorithm, why does promoting an element via repeated fair coin flips (rather than a fixed number of levels) let the skip list adapt to insertions without explicit rebalancing?
4. Why does reading a successful search backward turn the problem of bounding the number of search moves into a problem about counting fair coin flips?
5. What is the difference between showing that skip list search takes O(log n) in expectation and showing it takes O(log n) with high probability, and why does the lecture need both the warm-up lemma and Chernoff's bound to establish the stronger result?