Randomized QuickSort | Karger Min-Cut | Las Vegas vs Monte Carlo
Graduate
§1 — Interactive Simulation
Ready — Press Play or Next to begin.
Speed:
0
Operations
0
Comparisons
0 / 0
Step
—
n
RANDOMIZED-QUICKSORT(A, lo, hi):
p = RANDOM(lo, hi) // random pivot
swap(A[p], A[hi])
pivot_pos = PARTITION(A, lo, hi)
QUICKSORT(A, lo, pivot_pos-1)
QUICKSORT(A, pivot_pos+1, hi)
KARGER MIN-CUT (randomized):
while |V| > 2: randomly contract an edge
return remaining edge count
Repeat O(n^2 log n) times, return minimum
§2 — The Idea, Step by Step
Play rock-paper-scissors against a friend. If you always throw rock, they learn it and beat you every time. If you choose at random, they can’t plan against you — there is no "always-win" counter to exploit. Randomized algorithms borrow exactly this trick: by flipping a coin inside the algorithm, they leave no single input that a clever opponent can use to make them slow.
Sorting is the classic example. Ordinary QuickSort splits a pile around a chosen item (the pivot). If it always picks, say, the last item, then handing it an already-sorted list forces the most work possible. Randomized QuickSort instead grabs a random pivot each time, so no particular input is its enemy. Counting work in comparisons, a random pivot needs about $2n\ln n$ of them on average, while the bad fixed-pivot case needs about $n(n-1)/2$. For $n=100$ that is roughly $920$ versus $4950$ — more than five times fewer, just from one coin flip.
Two flavors. A Las Vegas algorithm is always correct and only its running time is random — Randomized QuickSort always sorts, it just occasionally takes longer. A Monte Carlo algorithm has a fixed running time but may be wrong, rarely, and you can shrink "rarely" as much as you like by repeating it. Karger’s min-cut is Monte Carlo: one run succeeds with probability only $\ge 2/n^2$, so you repeat about $n^2\ln n$ times and keep the best, dropping the failure chance to $\le 1/n$.
The precise reason QuickSort’s average is so good uses indicator variables: the elements at sorted ranks $i$ and $j$ are compared only if one of them is the first pivot drawn from the block between them, which happens with probability $2/(j-i+1)$. Adding this over every pair gives the expected comparison count $\sum_{in slider sets the input size and the preset menu chooses the input’s arrangement — Sorted, Reverse and Special are the kinds of inputs an adversary would hand a fixed-pivot sorter to slow it down.
Try this in the sim above.
(1) Drag the n slider across its range and press ↻ Reset: the Comparisons stat tracks $n(n-1)/2$, the quadratic cost of a full pass — the very number randomization shrinks toward $2n\ln n$.
(2) Switch the preset between Sorted and Reverse and step with Next ▶: the comparisons stay equal while the Operations (swaps) swing from none to the maximum, showing how the arrangement of the input, not just its size, decides the work — the lever an adversary pulls and randomness takes away.
(3) Choose Random and hit ↻ Reset a few times: every reset reshuffles, so no two traces match — the same unpredictability a random pivot injects so that no single input can ever be its worst case.
§3 — Algorithm Analysis & Derivation
Symbol
Meaning
n
Input size
T(n)
Time complexity function
W(n)
Worst-case complexity
A(n)
Average / amortized complexity
Φ(S)
Potential function of data structure state S
α(n)
Inverse Ackermann function (~constant)
Step 1 — Two Types of Randomized Algorithms. Las Vegas: always correct, random runtime. Example: Randomized QuickSort — always sorts correctly, expected O(n log n) time. Monte Carlo: fixed runtime, correct with high probability. Example: Karger's min-cut — O(n²) per run, correct with probability ≥ 2/n².
Step 2 — Randomized QuickSort Analysis. Random pivot: each element equally likely to be pivot. Expected comparisons: E[C] = ∑_{i<j} Pr[i and j are compared] = ∑_{i<j} 2/(j-i+1). Summing: E[C] = 2n ∑_{k=1}^n 1/k = 2n H_n ≈ 2n ln n ≈ 1.386 n log_2 n.
Step 3 — Why E[C] = 2/(j-i+1)? Elements i and j are compared iff one of them is the first pivot chosen from {i, i+1, ..., j}. Probability: 2 / (j - i + 1) (two of the j-i+1 elements are i and j). This elegant indicator random variable argument is due to Blum, Floyd, Pratt, Rivest, Tarjan.
Step 4 — Karger's Min-Cut Algorithm. Randomly contract a random edge (merge two vertices, keep multi-edges, remove self-loops). Repeat until 2 vertices remain. Remaining edges = a cut. Probability of finding minimum cut in one run: ≥ 2/n². Run n² log n times: error probability ≤ 1/n. Total: O(n² log n) · O(n²) = O(n⁴ log n). Karger-Stein: O(n² log³ n).
Step 5 — Randomization vs Determinism. Often randomized algorithms are simpler to implement, faster in practice, and avoid adversarial inputs. Adversary cannot predict random choices. Derandomization: replace random choices with deterministic constructions (pseudorandom generators, ε-nets). Sipser-Gács-Lautemann: BPP ⊆ Σ_2 (randomized ⊆ second level of polynomial hierarchy).
Step 6 — Applications. Randomized algorithms used in: Miller-Rabin primality test (Monte Carlo). Hashing (universal hash families). Skip lists (randomized balanced structure). Randomized rounding (LP relaxation to integer solutions). Streaming algorithms (approximate count, heavy hitters). Cryptography (key generation).
§4 — Frequently Asked Questions
What is the difference between Las Vegas and Monte Carlo? concept+
Las Vegas: output is ALWAYS correct, running time is random (expected polynomial). Example: Randomized QuickSort, randomized hashing. Monte Carlo: running time is FIXED (deterministic), output is correct with HIGH PROBABILITY. Example: Karger min-cut, Miller-Rabin primality. Can reduce error by repeating.
Why is randomized QuickSort better than deterministic worst-case? concept+
Deterministic QuickSort with fixed pivot: adversary can craft input (sorted array) to trigger O(n²). Random pivot: no adversarial input exists — the adversary doesn't know which pivot will be chosen. Expected O(n log n) regardless of input. The randomization breaks adversarial worst cases.
Where are randomized algorithms used in cryptography? applied+
RSA key generation: random prime selection using Miller-Rabin. Diffie-Hellman: random secret exponents. AES: random initialization vectors. Zero-knowledge proofs: random challenges. Without randomness, many cryptographic protocols become insecure or deterministically breakable.
What is a high-probability bound? complex+
'With high probability': probability ≥ 1 - 1/n^c for some constant c. Much stronger than 'with constant probability'. QuickSort with random pivot: O(n log n) time with high probability (not just in expectation). Proof: probability of taking more than 4n log n steps is at most 1/n (Chernoff bound).
How does Karger's algorithm achieve the correct probability bound? deep+
Min cut has k edges. At each contraction: probability of contracting a min-cut edge ≤ k/(n(n-1)/2) = 2/n(n-1) ≤ 2/n. Probability of NOT contracting any min-cut edge after n-2 contractions: ∏_{i=0}^{n-3} (1 - 2/(n-i)) ≥ ∏ (1-2/j) = 2/n(n-1) ≥ 2/n². Running n²/2 log n times: probability of missing min-cut each time ≤ 1/n.
What is the principle of deferred decisions? nonobv+
In randomized algorithm analysis: defer the random choices to the moment they affect the algorithm. For QuickSort: imagine elements have random ranks; defer the 'which element is pivot' decision to when we ask 'are elements i and j compared?'. This clean separation of randomness from algorithm logic simplifies proofs dramatically.
§5 — Misconceptions & Implementation Errors
Conceptual Misconceptions
✗ Las Vegas algorithms may give wrong answers.
✓ Las Vegas algorithms ALWAYS give correct answers — only the running time is random. Monte Carlo may give wrong answers (with bounded probability).
✗ Randomized algorithms are always faster than deterministic ones.
✓ Not always. Some problems have optimal deterministic algorithms. Randomization helps primarily when: adversarial inputs exist, natural distributions are unknown, or simple randomized solutions beat complex deterministic ones in practice.
✗ Running a Monte Carlo algorithm once is sufficient.
✓ Monte Carlo has error probability p per run. Run k times independently, take majority/minimum: error probability ≤ p^k. Must run enough times to reduce error to acceptable level.
Implementation Errors
✗ Random pivot guarantees O(n log n) worst case.
✓ Random pivot gives O(n log n) EXPECTED and with high probability. Worst case is still O(n²) (if all coin flips are bad). The probability of O(n²) is exponentially small but nonzero.
✗ RANDOM(lo,hi) is O(1) in all models.
✓ Generating a true random number requires a random source (hardware RNG, OS entropy). Pseudorandom generators are deterministic and O(1) per call, but not truly random. For algorithm analysis, we assume true randomness. In practice, PRNG is sufficient.
✗ Karger's algorithm finds the min-cut in O(n^2) time.
✓ One run of Karger is O(n²) but succeeds with only 2/n² probability. Must repeat O(n² log n) times for high-probability guarantee: total O(n⁴ log n). Karger-Stein reduces this to O(n² log³ n) using recursive contraction.