Back to Study Material Data Structures and Algorithms

Randomized Algorithms

Randomized algorithms introduce deliberate randomness into their logic, using random choices to achieve better expected performance or simpler implementati...

Randomized Algorithms

Types of Randomized Algorithms and Probabilistic Analysis

Randomized algorithms introduce deliberate randomness into their logic, using random choices to achieve better expected performance or simpler implementation compared to deterministic alternatives. They fall into two broad categories. Las Vegas algorithms always produce a correct answer but have random running time — quicksort with random pivot selection is the canonical example. Monte Carlo algorithms always run in bounded time but may produce an incorrect answer with some small probability — the Miller-Rabin primality test is a classic example.

Probabilistic analysis provides the theoretical foundation for understanding randomized algorithms. By analyzing the expected value of the running time over all possible random choices, we can show that randomized quicksort runs in O(n log n) expected time even though its worst case is O(n^2). The key insight is that a random permutation of the input makes it exponentially unlikely to always choose a bad pivot, so the expected depth of recursion is O(log n).

The union bound and Markov's inequality are the two most commonly used probabilistic tools for algorithm analysis. The union bound says P(A1 or A2 or ... or Ak) <= sum of P(Ai), which lets you bound the probability that any bad event occurs. Markov's inequality says P(X >= t) <= E[X] / t for non-negative X, which converts an expected-value bound into a tail bound. Together, these tools let you prove that randomized algorithms fail with negligibly small probability for large inputs.

Randomized Quicksort, Quickselect, and Skip Lists

Randomized quicksort selects the pivot uniformly at random from the remaining elements before each partition step. This single modification transforms an algorithm with O(n^2) worst-case performance into one with O(n log n) expected performance, with the probability of significantly exceeding the expected time being astronomically small for large n. The expected number of comparisons is exactly 2n ln n, which is roughly 1.39 n log2 n.

Quickselect finds the k-th smallest element of an unsorted array in O(n) expected time using the same random pivot strategy. After partitioning, the pivot lands at some position p. If p equals k, you are done. If k < p, recurse on the left partition; if k > p, recurse on the right. The expected number of comparisons is O(n) because the expected work at each level decreases geometrically as the recursion narrows in on the target element. The worst case remains O(n^2) but occurs with probability that decreases exponentially in n.

Skip lists are a randomized data structure providing O(log n) expected time for search, insertion, and deletion without the complex rebalancing required by balanced BSTs. Each element is promoted to higher levels with probability 1/2 (or 1/4 for a smaller constant factor). Search traverses from the highest level downward, skipping large spans at high levels and refining at lower levels. The expected height of the skip list is O(log n), and the expected total number of nodes across all levels is O(n). Skip lists are simpler to implement correctly than red-black trees and are used in Redis and LevelDB.

Hashing, Bloom Filters, and Miller-Rabin Primality Testing

Universal hashing chooses a hash function randomly from a family of functions to guarantee that any fixed input has low collision probability regardless of its content. A simple universal family for integer keys in [0, p) with table size m is h(k) = ((ak + b) mod p) mod m for random a in [1, p) and b in [0, p), where p is prime. For any two distinct keys x and y, P(h(x) = h(y)) <= 1/m. This probabilistic guarantee holds even against adversarial inputs, unlike fixed hash functions.

Bloom filters are space-efficient probabilistic data structures that answer set membership queries. They use k independent hash functions to map each element to k positions in a bit array of size m. To insert, set all k bits. To query, check all k bits — if any is 0, the element is definitely absent; if all are 1, the element is probably present (false positives are possible). With m = 10 bits per element and k = 7 hash functions, the false positive rate is approximately 1%. Bloom filters are used in databases, network routers, and spell checkers.

The Miller-Rabin primality test is a Monte Carlo algorithm that determines whether n is prime. For each random witness a, it checks a necessary condition for primality derived from Fermat's little theorem and the structure of square roots of 1 modulo n. If n is composite, at least 3/4 of all possible witnesses will detect this, so running k independent trials gives a false positive rate of at most 4^(-k). With k = 20 trials, the error probability is less than 10^(-12), sufficient for all practical purposes. For n < 3.2 * 10^18, testing the specific witnesses {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} gives a deterministic correct answer.