47.05.02 · theoretical-cs / randomized-algorithms

Randomized Algorithms: Quicksort, Skip Lists, and Treaps

shipped3 tiersLean: none

Anchor (Master): Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) §5.3, §7.3-7.4, §12.4; Motwani & Raghavan 1995 Randomized Algorithms (Cambridge) Ch. 1-2 (Las Vegas vs Monte Carlo, expected running time analysis, skip lists and treaps)

Intuition Beginner

Imagine you are sorting a deck of cards. One strategy: pick a card at random, split the deck into cards smaller and cards larger, then sort each half. This is randomized quicksort. The random choice means you never get stuck with a bad split — on average, the splits are good enough to sort quickly.

Randomized algorithms use coin flips (or more generally, random number generation) to make decisions during execution. There are two flavours. Las Vegas algorithms always produce the correct answer, but their running time varies. Monte Carlo algorithms run in a fixed time but might produce a wrong answer with small probability.

Randomized quicksort is Las Vegas: it always correctly sorts the array, and its expected running time is $O (n lo g n)$ regardless of the input. The randomness is in the algorithm, not the input. No adversary can craft a worst-case input because the pivot choice is random.

Skip lists extend this idea to dictionaries. Instead of maintaining a complex balance invariant (like red-black trees), you build multiple levels of linked lists where each node is promoted to a higher level with probability 1/2. Search starts at the top level and drops down, achieving $O (lo g n)$ expected time with a simple implementation.

Treaps combine binary search trees with random priorities. Each key gets a random priority, and the tree is a heap on priorities. The randomness of priorities ensures the tree is balanced in expectation, giving $O (lo g n)$ expected time for all operations.

Visual Beginner

Skip list for keys {3, 7, 12, 21, 35, 42}:

Level 3:  HEAD ─────────────────────────→ 42
Level 2:  HEAD ──────→ 12 ──────────────→ 42
Level 1:  HEAD ──→ 7 ──→ 12 ──→ 21 ────→ 42
Level 0:  HEAD → 3 → 7 → 12 → 21 → 35 → 42

Each node was promoted to higher levels with probability 1/2. To search for 21: start at level 3, move right (42 is too large), drop to level 2, move right (12), move right (42 too large), drop to level 1, move right (21 found).

Structure	Expected search time	Worst case	Code complexity
Sorted array	$O (lo g n)$	$O (lo g n)$	Simple but insert is $O (n)$
Red-black tree	$O (lo g n)$	$O (lo g n)$	Complex
Skip list	$O (lo g n)$	$O (n)$ unlikely	Simple
Treap	$O (lo g n)$	$O (n)$ unlikely	Moderate

Worked example Beginner

We sort the array [4, 1, 7, 3, 6] using randomized quicksort.

Step 1. Choose a random pivot from [4, 1, 7, 3, 6]. Suppose we pick 4 (index 0).

Partition: elements less than 4 go left, elements greater go right.

Left: [1, 3]. Right: [7, 6]. Pivot: [4].

Step 2a. Sort left [1, 3]. Choose random pivot: suppose 1.

Partition: left [], right [3]. Pivot [1].

Result: [1, 3].

Step 2b. Sort right [7, 6]. Choose random pivot: suppose 6.

Partition: left [], right [7]. Pivot [6].

Result: [6, 7].

Combine. [1, 3] + [4] + [6, 7] = [1, 3, 4, 6, 7].

The pivot choices led to a balanced partition (2 elements on each side of 4). In the worst case, if we always picked the smallest element, each partition would give 0 and $n - 1$ elements, leading to $O (n^{2})$ time. But the probability of consistently bad choices is exponentially small.

Check your understanding Beginner

Formal definition Intermediate+

Definition (Las Vegas algorithm). A Las Vegas algorithm is a randomized algorithm that always produces a correct output but whose running time $T$ is a random variable. The expected running time is $E [T]$ .

Definition (Monte Carlo algorithm). A Monte Carlo algorithm is a randomized algorithm that runs in deterministic time but may produce an incorrect output with probability at most $δ$ (the error probability).

Definition (randomized quicksort). Randomized quicksort selects a pivot uniformly at random from the subarray $A [p .. r]$ and partitions around it:

RANDOMIZED-QUICKSORT(A, p, r):
  if p < r:
    q = RANDOMIZED-PARTITION(A, p, r)
    RANDOMIZED-QUICKSORT(A, p, q - 1)
    RANDOMIZED-QUICKSORT(A, q + 1, r)

Theorem (expected running time of randomized quicksort). The expected running time of randomized quicksort on an array of $n$ elements is $O (n l g n)$ .

Proof sketch. Let $z_{1}, \dots, z_{n}$ be the elements in sorted order. Define indicator $X_{ij} = 1$ if $z_{i}$ and $z_{j}$ are compared during the algorithm. The total number of comparisons is $X = \sum_{i < j} X_{ij}$ . By linearity of expectation, $E [X] = \sum_{i < j} Pr [X_{ij} = 1]$ .

Two elements $z_{i}$ and $z_{j}$ are compared if and only if one of them is chosen as a pivot before any element between them (i.e., $z_{i + 1}, \dots, z_{j - 1}$ ) is chosen. Among the set ${z_{i}, z_{i + 1}, \dots, z_{j}}$ , each element is equally likely to be chosen as pivot first. So $Pr [X_{ij} = 1] = 2/ (j - i + 1)$ .

Therefore $E [X] = \sum_{i < j} \frac{2}{j - i + 1} = \sum_{ℓ = 2}^{n} \frac{2 ( n - ℓ + 1 )}{ℓ} \leq 2 n \sum_{ℓ = 2}^{n} \frac{1}{ℓ} \leq 2 n \cdot H_{n} = O (n l g n)$ . $□$

Definition (skip list). A skip list for a sorted set $S$ of $n$ elements is a collection of linked lists $L_{0}, L_{1}, \dots, L_{h}$ where $L_{0}$ contains all elements of $S$ in sorted order, and each element is promoted from $L_{i}$ to $L_{i + 1}$ independently with probability $1/2$ . The maximum level $h$ is $O (lo g n)$ with high probability.

Theorem (skip list search cost). The expected cost of a search in a skip list with $n$ elements is $O (l g n)$ .

Definition (treap). A treap for a set of $n$ key-priority pairs $(k_{i}, p_{i})$ is a binary search tree on the keys that is simultaneously a max-heap on the priorities. When priorities are chosen independently and uniformly at random, the expected height of the treap is $O (l g n)$ .

Counterexamples to common slips

"Randomized quicksort has $O (n^{2})$ worst case so it is bad." The worst case is exponentially unlikely. For any fixed input, the probability of $O (n^{2})$ time is at most $1/ n^{c}$ for any constant $c$ . In practice, randomized quicksort is faster than mergesort due to better cache behaviour.
"Skip lists are probabilistically balanced but unreliable." The failure probability is exponentially small. The probability that a skip list search takes more than $c lo g n$ steps is at most $1/ n^{c - 1}$ for appropriate constants.
"Treaps can degenerate into linked lists." In expectation, the height is $O (lo g n)$ . The probability of height exceeding $c lo g n$ is exponentially small. Treaps are "balanced with high probability."

Key theorem with proof Intermediate+

Theorem (treap expected height). The expected height of a treap on $n$ keys with random priorities is $O (l g n)$ .

Proof. Let $X_{ij}$ be the indicator that node $i$ is an ancestor of node $j$ (or vice versa). The depth of node $j$ is $D_{j} = \sum_{i \neq = j} X_{ij}$ and the height is $H = max_{j} D_{j}$ .

Node $i$ is an ancestor of node $j$ iff among the nodes on the path from $i$ to $j$ in the key ordering, node $i$ has the highest priority. Since priorities are random, this probability is $1/∣ i - j + 1∣$ for each pair.

By linearity of expectation, $E [D_{j}] = \sum_{i \neq = j} 1/∣ i - j ∣ + 1 \leq 2 H_{n} = O (l g n)$ where $H_{n}$ is the $n$ -th harmonic number.

For the height, $E [H] = E [max_{j} D_{j}]$ . While the maximum of expectations can exceed the expectation of the maximum, a more careful analysis using the fact that $D_{j}$ is the sum of independent indicators (they are not independent, but weakly correlated) gives $E [H] = O (l g n)$ . More precisely, by a result of Devroye (1986), $E [H] \leq 4.311 l g n$ for large $n$ . $□$

Bridge. Randomized data structures are the foundational reason simple algorithms can match the performance guarantees of deterministic structures: randomisation replaces complex invariant maintenance with probabilistic balance. This builds toward the hashing algorithms of 47.05.01, where universal hashing achieves $O (1)$ expected performance with simpler code than deterministic alternatives, and it appears again in 47.05.03 where primality testing uses randomness to achieve polynomial time with high probability. The central insight is that random choices are "good on average" — this is exactly the principle that makes randomized quicksort, skip lists, and treaps work. Putting these together yields a design philosophy: when a deterministic invariant is expensive to maintain, replace it with a random choice that achieves the same effect in expectation.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove that the probability that two elements $z_{i}$ and $z_{j}$ (with $i < j$ ) are compared in randomized quicksort is exactly $2/ (j - i + 1)$ .

Hint

$z_{i}$ and $z_{j}$ are compared iff one of them is the first pivot chosen from ${z_{i}, z_{i + 1}, \dots, z_{j}}$ .

Answer

The elements $z_{i}, z_{i + 1}, \dots, z_{j}$ form a contiguous group in the sorted order. When quicksort processes a subarray containing this group, the first pivot chosen from this group determines which pairs are compared. If $z_{i}$ or $z_{j}$ is chosen first (probability $2/ (j - i + 1)$ ), then $z_{i}$ and $z_{j}$ are compared during the partition step. If any of $z_{i + 1}, \dots, z_{j - 1}$ is chosen first, then $z_{i}$ and $z_{j}$ are placed in different subarrays and will never be compared. So $Pr [X_{ij} = 1] = 2/ (j - i + 1)$ . Rubric: full credit for the "first pivot in the interval" argument.

Exercise 6 (hard, symbolic).

Prove that the expected depth of a node in a treap with $n$ keys and random priorities is at most $2 H_{n} - 1 = O (l g n)$ where $H_{n}$ is the $n$ -th harmonic number.

Hint

Let $D_{j}$ be the depth of node $j$ . Show that $Pr [j is ancestor of i] = 1/ (∣ i - j ∣ + 1)$ and sum over all $i$ .

Answer

Node $j$ is an ancestor of node $i$ in the treap iff $j$ has the highest priority among all keys in the range $[min (i, j), max (i, j)]$ . Since priorities are random, this probability is $1/ (max (i, j) - min (i, j) + 1) = 1/ (∣ i - j ∣ + 1)$ .

The depth of node $j$ is the number of ancestors of $j$ (excluding $j$ itself). Node $i \neq = j$ is an ancestor of $j$ with probability $1/ (∣ i - j ∣ + 1)$ . By linearity of expectation:

$E [D_{j}] = \sum_{i \neq = j} \frac{1}{∣ i - j ∣ + 1} = \sum_{k = 1}^{n - j} \frac{1}{k + 1} + \sum_{k = 1}^{j - 1} \frac{1}{k + 1} \leq 2 \sum_{k = 1}^{n} \frac{1}{k} = 2 H_{n} - 2 < 2 ln n$ .

Rubric: full credit for the ancestor probability and the harmonic sum.

Exercise 9 (hard, short answer).

Prove that the expected search cost in a skip list is $O (lo g n)$ . Analyse the backward search path from the target node to the head.

Answer

Search in a skip list starts at the topmost level and moves right, dropping down when the next node exceeds the target. Consider the backward analysis: starting from the target node, trace the search path backwards to the head. At each step, either the previous node is at the same level (moved right) or at a higher level (dropped down). Each backward step either moves left on the same level or moves up one level. Moving up happens with probability 1/2 (because the node at the next level up was promoted). The expected number of steps to reach level 0 and the head is bounded by the number of level-ups ( $O (lo g n)$ expected levels) plus the number of horizontal moves per level ( $O (1)$ expected, because each sequence of horizontal moves at a given level is bounded by a geometric random variable with parameter 1/2). Total expected cost: $O (lo g n)$ .

Rubric: full credit for the backward analysis.

Lean formalization Intermediate+

Mathlib has Probability.ProbabilityMassFunction, Data.Tree, and Sort.QuickSort (a deterministic quicksort), but no formalisation of randomized quicksort, skip lists, or treaps. The foundational gap is the absence of a probabilistic computation framework that tracks expected running time, the indicator-variable analysis of quicksort comparisons, and the geometric-random-variable analysis of skip list levels. A RandT (randomised computation) monad with an expected-cost measure would be the load-bearing first step. This unit ships without a lean_module.

Advanced results Master

Three results sharpen the theory of randomized algorithms for sorting and searching.

Theorem 1 (high-probability bound for quicksort). With probability at least $1 - 1/ n^{c}$ (for any constant $c > 0$ ), randomized quicksort runs in $O (n lo g n)$ time.

This follows from a Chernoff-bound analysis of the number of comparisons. The tail decays exponentially, so even moderate deviations from the expected $2 n ln n$ comparisons are unlikely. This means randomized quicksort is not just good on average — it is good with overwhelming probability.

Theorem 2 (skip list with high probability). All operations (search, insert, delete) in a skip list with $n$ elements run in $O (l g n)$ time with probability at least $1 - 1/ n^{c}$ for any constant $c$ .

The proof uses the fact that the skip list height is $O (lo g n)$ with high probability (union bound on geometric random variables) and that the expected number of horizontal moves per level is $O (1)$ with exponentially small tail. This matches the guarantees of balanced search trees without the complex rebalancing logic ^{[Motwani & Raghavan Ch. 2]}.

Theorem 3 (treap split and merge). Treaps support split and merge operations in $O (l g n)$ expected time.

Split( $T$ , $k$ ) divides treap $T$ into two treaps at key $k$ . Merge( $T_{1}$ , $T_{2}$ ) combines two treaps (all keys in $T_{1}$ are less than all keys in $T_{2}$ ). Both operations are fundamental building blocks for more advanced data structures like interval trees and link-cut trees.

Synthesis. Randomized data structures are the foundational reason simple algorithms can achieve logarithmic-time performance: randomisation replaces deterministic invariants with probabilistic ones that hold with high probability. The central insight is that random choices are "good on average" — this is exactly the principle that unifies randomized quicksort, skip lists, and treaps, despite their very different structures. This builds toward the broader theory of randomized algorithms, where randomness serves as a resource that can simplify algorithm design, improve performance, and enable computations that are difficult or impossible deterministically. Putting these together with the universal hashing of 47.05.01 and the primality testing of 47.05.03 yields a unified framework for using randomness as an algorithmic tool.

Full proof set Master

Proposition 1 (randomized quicksort expected comparisons). The expected number of comparisons in randomized quicksort on $n$ distinct elements is at most $2 n ln n$ .

Proof. Let $z_{1} < z_{2} < \dots < z_{n}$ be the elements in sorted order. Define $X_{ij} = [z_{i} and z_{j} are compared]$ . Total comparisons: $X = \sum_{1 \leq i < j \leq n} X_{ij}$ .

Claim: $Pr [X_{ij} = 1] = \frac{2}{j - i + 1}$ .

The elements ${z_{i}, z_{i + 1}, \dots, z_{j}}$ form a contiguous range in sorted order. When quicksort first selects a pivot from this range, $z_{i}$ and $z_{j}$ are compared iff the pivot is $z_{i}$ or $z_{j}$ (then one is compared to all others in the range). If any $z_{k}$ with $i < k < j$ is the pivot, then $z_{i}$ and $z_{j}$ are placed in different subarrays and never compared. Since the pivot is chosen uniformly at random, the first pivot from this range is equally likely to be any of the $j - i + 1$ elements. So $Pr [X_{ij} = 1] = 2/ (j - i + 1)$ .

E [X] = i < j \sum \frac{2}{j - i + 1} = ℓ = 1 \sum n - 1 \frac{2 ( n - ℓ )}{ℓ + 1} \leq 2 n k = 2 \sum n \frac{1}{k} \leq 2 n \int_{1}^{n} \frac{d x}{x} = 2 n ln n . □

Proposition 2 (skip list height bound). The height of a skip list with $n$ elements exceeds $c l g n$ with probability at most $n^{1 - c}$ .

Proof. Each element is promoted to level $k$ with probability $2^{- k}$ . The height $H = max_{i} L_{i}$ where $L_{i} \sim Geom (1/2)$ . By union bound:

Pr [H \geq c l g n] = Pr [\exists i : L_{i} \geq c l g n] \leq n \cdot Pr [L_{1} \geq c l g n] = n \cdot 2^{- c l g n} = n \cdot n^{- c} = n^{1 - c} . □

Proposition 3 (treap expected depth). The expected depth of any node in a treap with $n$ keys and random priorities is at most $2 H_{n} - 1$ .

Proof. The depth of node $j$ is $D_{j} = \sum_{i \neq = j} [i is ancestor of j]$ . Node $i$ is an ancestor of node $j$ iff $i$ has the highest priority among ${z_{m i n (i, j)}, \dots, z_{m a x (i, j)}}$ . Since priorities are uniform and independent, this probability is $1/ (∣ i - j ∣ + 1)$ . So:

E [D_{j}] = i \neq = j \sum \frac{1}{∣ i - j ∣ + 1} = k = 1 \sum n - j \frac{1}{k + 1} + k = 1 \sum j - 1 \frac{1}{k + 1} \leq 2 (H_{n} - 1) = 2 H_{n} - 2 < 2 ln n . □

Connections Master

47.05.01 — Universal and perfect hashing use randomisation to achieve expected $O (1)$ dictionary operations; skip lists and treaps achieve $O (lo g n)$ for comparison-based structures.
47.04.02 — Red-black trees provide deterministic $O (lo g n)$ worst-case guarantees; treaps provide the same expected bound with simpler code.
47.04.01 — Amortized analysis bounds the total cost over sequences; randomized analysis bounds the expected cost per operation.
50.03.01 — Big-O and expected-value analysis are the analytical tools used throughout.

Historical & philosophical context Master

Randomized quicksort was analysed by Hoare (1962) in his original paper on quicksort, where he noted that random pivot selection avoids worst-case behaviour. The formal analysis using indicator random variables is due to the textbook treatment by CLRS ^{[CLRS §7.4]}.

Skip lists were invented by William Pugh in 1990. His motivation was to create a probabilistic alternative to balanced trees that is simpler to implement and has comparable performance. The key insight was that multiple levels of linked lists with geometrically decreasing density mimic the structure of a balanced tree without requiring explicit balancing ^{[Motwani & Raghavan Ch. 2]}.

Treaps were introduced by Aragon and Seidel in 1989 (published 1996). The name "treap" was coined by Cecilia Aragon, who was also a championship-level rock climber. The treap's simplicity — a BST with random priorities — demonstrates a philosophical point: randomness can replace algorithmic cleverness. Instead of a complex rebalancing algorithm, the treap relies on the fact that random priorities produce balanced trees in expectation.

The broader philosophical point is that randomness is a computational resource. Just as time and space constrain what algorithms can do, randomness expands what can be done efficiently. The question of whether randomness genuinely helps (the BPP vs P question of 47.03.01) remains one of the central open problems in complexity theory.

Bibliography Master

@book{clrs2022,
  author    = {Cormen, Thomas H. and Leiserson, Ronald L. and Rivest, Clifford and Stein, Christopher},
  title     = {Introduction to Algorithms},
  edition   = {4th},
  publisher = {MIT Press},
  year      = {2022},
}
@book{motwani1995,
  author    = {Motwani, Rajeev and Raghavan, Prabhakar},
  title     = {Randomized Algorithms},
  publisher = {Cambridge University Press},
  year      = {1995},
}
@article{pugh1990skip,
  author  = {Pugh, William},
  title   = {Skip Lists: A Probabilistic Alternative to Balanced Trees},
  journal = {Communications of the ACM},
  volume  = {33},
  number  = {6},
  pages   = {668--676},
  year    = {1990},
}
@article{aragon1989randomized,
  author  = {Aragon, Cecilia R. and Seidel, Raimund},
  title   = {Randomized Search Trees},
  journal = {Algorithmica},
  volume  = {16},
  pages   = {464--497},
  year    = {1996},
  note    = {Preliminary version 1989},
}

Prerequisites

47.05.01

Tier anchors

beginner: Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) §5.3, §7.3-7.4 (randomized algorithms as algorithms that use coin flips to make decisions, expected running time, randomized quicksort as the canonical example)
intermediate: Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) §5.3, §7.3-7.4, §12.4 (randomized quicksort with expected O(n log n) time, skip lists as probabilistic balanced structures, treaps as BSTs with random heap priorities)
master: Cormen, Leiserson, Rivest & Stein 2022 Introduction to Algorithms 4e (MIT Press) §5.3, §7.3-7.4, §12.4; Motwani & Raghavan 1995 Randomized Algorithms (Cambridge) Ch. 1-2 (Las Vegas vs Monte Carlo, expected running time analysis, skip lists and treaps)

References

Cormen, T. H., Leiserson, R. L., Rivest, C. L. & Stein, C. — Introduction to Algorithms (4th ed.) · MIT Press (2022). Section 5.3 defines randomized algorithms as algorithms whose behaviour (not just running time) depends on random choices made during execution, with expected running time defined as $E [T (n)]$ over the random choices; Section 7.3 presents randomized quicksort where the pivot is chosen uniformly at random from the subarray, and Theorem 7.4 proves $E [T (n)] = O (n l g n)$ using the indicator random variable analysis counting comparisons; Section 7.4 analyses the expected running time by showing that each pair of elements is compared with probability at most $2/ (j - i + 1)$ ; Section 12.4 defines treaps as binary search trees where each node has a random priority and the tree is a max-heap on priorities, guaranteeing expected height $O (l g n)$ .
Motwani, R. & Raghavan, P. — Randomized Algorithms · Cambridge University Press (1995). Chapter 1 distinguishes Las Vegas algorithms (always correct, random running time) from Monte Carlo algorithms (may err with small probability, deterministic running time); Chapter 2 analyses randomized quicksort and skip lists, proving that skip lists support search, insert, and delete in $O (l g n)$ expected time with high probability, using $O (n)$ expected space.

Estimated time

beginner: 15m
intermediate: 40m
master: 75m