What Is a Randomized Algorithm? Expected Complexity, Explained

You have an array of a million integers. You need to sort it. You pick the last element as your pivot, and you get unlucky: the array is already sorted. Every partition produces one element on the left, everything else on the right. You just ran O(n²) quicksort.

Congratulations. You've discovered adversarial inputs the hard way.

Now flip a coin instead. The probability that your pivot keeps landing in the worst position is so small it's effectively zero.

That's randomized algorithms. You inject a random choice to sidestep adversarial inputs, then analyze what happens on average over all possible coin flips. The expected time complexity is often as good as the deterministic worst case, with a much simpler correctness argument. Sometimes randomness is the smartest move.

Las Vegas Guarantees Correctness. Monte Carlo Guarantees Speed.

Every randomized algorithm belongs to one of two camps, and the distinction matters.

Las Vegas algorithms always return the correct answer. Only the runtime is random. Randomized quicksort always sorts correctly. You might finish in O(n log n), or theoretically hit O(n²), but the output is always sorted. The randomness affects only how long it takes. Think of it as the reliable friend who always shows up. Just maybe at 2am.

Monte Carlo algorithms flip this. They run in bounded time but may return a wrong answer with some controlled probability. Miller-Rabin primality testing is the textbook example. Each round has a 1/4 false positive rate. Run 50 rounds and the error probability drops below 2^(-100). Still technically possible. Practically impossible. In RSA key generation, a few extra rounds cost microseconds and reduce the error probability below the rate of cosmic ray bit flips. When your code fails less often than ambient radiation corrupts your server memory, that's a shipping product.

Bloom filters are Monte Carlo too. They tell you an element is "probably in the set" or "definitely not in the set." The false positive rate is bounded by design, never zero.

For coding interviews, Las Vegas algorithms dominate. You're expected to state expected time complexity and understand what the worst case looks like, not reason about probabilistic correctness.

Randomized Quicksort: Why Expected O(n log n)?

The problem with deterministic quicksort is adversarial inputs. Always pick the last element as pivot, and anyone can hand you a sorted array to crater your performance. Random pivot selection breaks this.

import random

def quicksort(arr, lo, hi):
    if lo >= hi:
        return
    pivot_idx = random.randint(lo, hi)
    arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]
    p = partition(arr, lo, hi)
    quicksort(arr, lo, p - 1)
    quicksort(arr, p + 1, hi)

def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1

The formal argument uses indicator variables. For any two elements i and j, define X_ij = 1 if they get compared during the sort, 0 otherwise. By linearity of expectation, the total expected comparisons equals the sum of E[X_ij] across all pairs.

Two elements are compared exactly when one of them is chosen as pivot before any element between them in sorted order. There are |i - j| + 1 candidates for that pivot slot. So E[X_ij] = 2 / (|i - j| + 1). Sum over all pairs and you get 2n ln(n) + O(n). That's O(n log n).

The intuition: a random pivot sits in the middle 50% of the array with probability 1/2. When it does, both subproblems shrink to at most 3n/4 elements. You need about two tries before a "good" pivot. O(1) expected work per level, O(log n) expected levels. The math agrees with the intuition, which is rare and delightful.

Sorted array vs random pivot: O(n²) unbalanced splits on the left, O(n log n) balanced splits on the right

Worth noting: Python's built-in sort is Timsort, a hybrid of insertion sort and merge sort with a guaranteed O(n log n) worst case. When you reach for random.randint in an interview and implement quicksort from scratch, you're choosing expected performance over the stronger deterministic guarantee. Know what you're trading and say it out loud. Interviewers absolutely notice the difference between "I used random pivot" and "I used random pivot because it breaks adversarial inputs at the cost of a probabilistic guarantee."

Quickselect Skips the Sort

Quickselect uses the same pivot trick to find the k-th smallest element without fully sorting. After each partition, you recurse into only the side containing the target index.

def quickselect(arr, lo, hi, k):
    if lo == hi:
        return arr[lo]
    pivot_idx = random.randint(lo, hi)
    arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]
    p = partition(arr, lo, hi)
    if k == p:
        return arr[p]
    elif k < p:
        return quickselect(arr, lo, p - 1, k)
    else:
        return quickselect(arr, p + 1, hi, k)

With probability at least 1/2, the random pivot falls in the middle half of the sorted order, reducing the problem to at most 3n/4 elements. The recurrence is T(n) = O(n) + T(3n/4). That geometric series sums to O(n). Quickselect finds the median of a million elements in expected linear time. Sorting first costs O(n log n), with no upside. It's the algorithmic equivalent of driving to a destination that's two blocks away. You'll get there. Just not optimally.

See the full Quickselect walkthrough for the median-of-medians deterministic variant, which gives a true O(n) worst-case guarantee at the cost of a larger constant.

The Data Structures That Roll Dice

Red-black trees are a marvel of engineering. They're also the kind of code that makes senior engineers stare into the middle distance when you mention rotations. Someone looked at all of that and said: what if we just used a random number instead?

A skip list is a layered linked list where each node is promoted to the next level by a coin flip. The expected height of any node is O(log n) because the probability of reaching level k is (1/2)^k. With high probability, a skip list supports search, insert, and delete in O(log n) without ever rebalancing. No rotations. No color bits. Just coins.

A treap combines a BST with a heap. Each node stores a key (BST order) and a random priority (heap order). The random priorities keep the tree balanced in expectation: the expected height is O(log n) for the same reason quicksort runs in O(n log n). No rotations, no color bits, no rebalancing passes.

Both skip lists and treaps trade the complexity of deterministic balancing code for the simplicity of one random number per node. That is a very good trade.

Reservoir Sampling: You Don't Need to Know the Length

Suppose you need to sample k elements uniformly at random from a stream of unknown length. You cannot store everything first. This sounds contrived until you are reading from a Kafka topic at 3am trying to figure out why production is on fire.

import random

def reservoir_sample(stream, k):
    reservoir = []
    for i, item in enumerate(stream):
        if i < k:
            reservoir.append(item)
        else:
            j = random.randint(0, i)
            if j < k:
                reservoir[j] = item
    return reservoir

When the i-th element arrives (0-indexed): if i < k, add it to the reservoir directly. Otherwise, keep it with probability k / (i + 1), replacing a random existing slot.

At any point in the stream, each element seen so far has exactly equal probability of being in the reservoir. The proof is by induction on stream length. The algorithm terminates in O(n) time and O(k) space regardless of how long the stream runs.

Reservoir sampling appears in interviews as "sample one random element from a linked list without knowing its length." That's reservoir sampling with k=1: at each step, keep the current element with probability 1/i.

Read the full reservoir sampling walkthrough for the complete inductive proof and follow-up variants.

Where Randomized Algorithms Show Up in Interviews

Quickselect is a direct question. "Find the k-th largest element in an unsorted array" (LeetCode 215) expects you to know that random pivot selection gives expected O(n) time. Most candidates sort first. That earns a technically correct answer and a very specific kind of disappointment from your interviewer.

Hash maps use randomization under the hood. Since Python 3.3, the hash function for strings uses a random seed per interpreter startup (PYTHONHASHSEED). This prevents hash-flooding attacks: an adversary crafts inputs that all collide in your map, degrading O(1) operations to O(n). Redis uses a per-map random seed for the same reason. When an interviewer asks about hash map worst-case performance, this is the context they're fishing for.

Expected vs. worst case is a standalone question. If an interviewer asks "what's the time complexity of your quicksort?" the correct answer is "expected O(n log n) with random pivot selection, O(n²) worst case." Saying just "O(n log n)" is technically wrong. Randomized algorithms give expected complexity guarantees, not worst-case ones. That distinction marks the difference between a 3 and a 4 on the algorithms dimension at most companies.

Senior-level follow-ups go deeper: can you prove why expected O(n log n) holds, not just assert it? Can you explain what "with high probability" means compared to "in expectation"? Can you describe a scenario where a Las Vegas algorithm is preferable to a Monte Carlo one? Knowing that randomized quicksort runs in expected O(n log n) is table stakes. Knowing why is what gets you hired.

SpaceComplexity simulates the real back-and-forth with follow-up questions about probability and complexity so you can practice articulating these ideas under time pressure before it counts.