Algorithmic Foundations

Randomization in Algorithms

Introducing randomness deliberately — a random pivot, a random hash seed, a random sample — can turn an algorithm's worst case from likely-to-happen into vanishingly-unlikely, trading a guarantee for an expected bound that holds regardless of input.

A randomized algorithm's running time is a random variable; "expected O(n log n)" means averaged over the algorithm's own coin flips, not over input distribution
Randomized quicksort with a random pivot has expected O(n log n) time on every input, because no adversary can target the randomness in advance
Reservoir sampling picks a uniform-random sample of unknown-size streaming data in one pass with O(k) memory
Randomized algorithms are either Las Vegas (always correct, random running time — randomized quicksort) or Monte Carlo (bounded time, small chance of a wrong answer)
Never use java.util.Random for anything security-sensitive; use SecureRandom there — this domain is about algorithmic randomness, not cryptographic randomness

Plain Quicksort with a fixed pivot rule (e.g. always the first element) has an adversarial worst case: already-sorted input drives it to Θ(n²). Picking the pivot uniformly at random each call does not change the worst-case input — sorted arrays still exist — but it makes the probability of hitting the bad case on any particular random choice vanishingly small, so the expected running time is Θ(n log n) no matter what the input is. The adversary can no longer choose a bad input, because the badness now depends on the algorithm's private coin flips, not on the data.

Reservoir sampling — a uniform random sample from an unknown-length stream

static int reservoirSample(Iterator<Integer> stream, Random rnd) {
    int reservoir = stream.next();       // first element is the initial sample
    int i = 1;
    while (stream.hasNext()) {
        int x = stream.next();
        i++;
        if (rnd.nextInt(i) == 0) {       // replace with probability 1/i
            reservoir = x;
        }
    }
    return reservoir;                    // every element seen so far had equal probability 1/i
}

One pass, O(1) extra memory for a sample of size 1 — extends to size k by keeping k slots.

Las Vegas vs. Monte Carlo randomized algorithms
Kind	Correctness	Running time	Example
Las Vegas	Always correct	Random (expected bound)	Randomized quicksort
Monte Carlo	Correct with high probability	Fixed/bounded	Miller–Rabin primality test