Introduction to Randomized Algorithms

Verified Sources

May 26, 2026

In computer science, a randomized algorithm is an algorithm that uses a source of random numbers to influence its behavior and decision-making during execution . Unlike a deterministic algorithm, which follows a rigid, predictable path for any given input, a randomized algorithm can behave differently across multiple runs on the exact same input.

This non-deterministic nature is not a bug; rather, it is a powerful design paradigm used to simplify algorithms, avoid worst-case adversarial inputs, and achieve faster expected time complexity .

Why Introduce Randomness?

In deterministic design, an adversary can often construct a specific input that triggers the worst-case running time of an algorithm (e.g., feeding a pre-sorted array to a standard deterministic quicksort). By incorporating random choices, the algorithm's performance no longer depends solely on the structure of the input, but on the outcomes of random coin flips. This effectively eliminates the "worst-case" input for practical purposes, as the probability of consistently making the worst random choices is infinitesimally small.

Structural Classification

Randomized algorithms are broadly classified into two main paradigms: Las Vegas and Monte Carlo .

GeeksforGeeks: Randomized Algorithms - Detailed classification and applications of randomized algorithms. ↩ ↩²
CMU: Randomized Algorithms - Expected running time analysis for Randomized Quicksort. ↩

What is a Randomized Algorithm? Explained with Examples

Why Use Randomness?

Randomness acts as an insurance policy against adversarial inputs. It prevents worst-case scenarios from being consistently triggered by making the algorithm's performance independent of input patterns.

Las Vegas vs. Monte Carlo Algorithms

The two primary classes of randomized algorithms differ fundamentally in how they trade off correctness and execution time .

Las Vegas algorithm:
- Correctness: Guaranteed to be 100% correct.
- Running Time: A random variable. We analyze its expected running time (the average time over all possible random choices).
- Example: Randomized Quicksort . It always produces a fully sorted array, but the number of comparisons depends on the random pivot choices.
Monte Carlo algorithm:
- Correctness: Probabilistic. There is a bounded probability of error (either false positives, false negatives, or both).
- Running Time: Bounded and deterministic (e.g., $O(n)$ or $O(1)$ ).
- Example: Karger's Min-Cut or the Miller-Rabin Primality Test .
- Mitigation: We can use amplification of probability to make the error rate astronomically small.

Dimension	Las Vegas Algorithm	Monte Carlo Algorithm
Correctness	Guaranteed to be correct	Probabilistic (may error)
Execution Time	Random variable (Expected)	Bounded / Deterministic
Primary Risk	High variance in execution time	Potential for incorrect results
Key Advantage	No correctness compromise	Predictable resource usage

GeeksforGeeks: Randomized Algorithms - Detailed classification and applications of randomized algorithms. ↩
CMU: Randomized Algorithms - Expected running time analysis for Randomized Quicksort. ↩
University of Washington: Randomized Algorithms Lecture Notes - Mathematical bounds on Miller-Rabin and Karger's Min-Cut. ↩ ↩²

Error Probability Reduction via Amplification

How independent runs exponentially decrease the error probability of Monte Carlo algorithms

Algorithm Walkthrough: Randomized Quicksort

1
Step 1
Choose an index $p$ from the array $A[L..R]$ uniformly at random. Swap $A[p]$ with the first element $A[L]$ to prepare for partitioning.
2
Step 2
Rearrange the array elements around the pivot $A[L]$ . All elements smaller than or equal to the pivot are shifted to the left, and all elements larger are shifted to the right.
3
Step 3
Recursively apply the randomized quicksort process to the left partition $A[L..p-1]$ and the right partition $A[p+1..R]$ .

1def quicksort(arr):\
2    if len(arr) <= 1:\
3        return arr\
4    pivot = arr[0]  # Always pick first element\
5    left = [x for x in arr[1:] if x <= pivot]\
6    right = [x for x in arr[1:] if x > pivot]\
7    return quicksort(left) + [pivot] + quicksort(right)\

Historical Milestones of Randomized Algorithms

The Monte Carlo Method

1940s

Stanislaw Ulam, John von Neumann, and Nicholas Metropolis develop the Monte Carlo method at Los Alamos to solve complex neutron diffusion problems."

Solovay-Strassen Primality Test

1977

Robert Solovay and Volker Strassen present the first randomized primality test, showing that randomness could solve number-theoretic problems much faster than deterministic ones."

Miller-Rabin Primality Test

1980

Michael O. Rabin refines the primality test into the highly efficient Miller-Rabin algorithm, which remains a cornerstone of modern cryptography today."

Karger's Min-Cut Algorithm

1993

David Karger introduces a simple, elegant randomized contraction algorithm for finding the global minimum cut in graphs, establishing new bounds in graph theory."

The Trap of Bad Random Number Generators

Randomized algorithms rely heavily on the assumption of truly independent, uniform random choices. Using weak pseudo-random number generators (PRNGs) can reintroduce worst-case behaviors or security vulnerabilities.

Advanced Concepts & FAQs

Knowledge Check

Question 1 of 3

Q1Single choice

What is the key distinguishing factor of a Las Vegas algorithm compared to a Monte Carlo algorithm?

It always produces the correct result, but its running time is a random variable.

It has a fixed running time, but its result may be incorrect with a certain probability.

It is always slower than deterministic alternatives.

It does not require any random number generator.

Explore Related Topics

Design and Analysis of Algorithms (DAA)

Breadth-First Search as an Uninformed Search Strategy

Breadth‑First Search (BFS) expands the shallowest frontier nodes first using a FIFO queue and does not employ any heuristic function, making it an uninformed (blind) search strategy.

Classified as uninformed search because it relies only on the problem definition, not on $h(n)$ or other estimates.
Complete for finite branching factors and optimal when all step costs are equal.
Tree‑search time and space are $O(b^{d})$ ; graph‑search runs in $O(|V|+|E|)$ time and $O(|V|)$ space.
Main weakness is exponential memory growth, so it suits shallow goals with ample memory.
If step costs vary, uniform‑cost search should be used instead of BFS.

Short Notes on Cook's Theorem, Randomized Algorithms, and Bin Packing

The notes cover Cook’s theorem establishing SAT as NP‑complete, the design and analysis of randomized (Las Vegas and Monte Carlo) algorithms, and the NP‑hard bin‑packing problem with its common heuristics and approximation guarantees.

Cook’s theorem shows every language $L\in\mathrm{NP}$ reduces to SAT via a polynomial‑time function $f$ such that $x\in L\iff f(x)\in\mathrm{SAT}$ , making SAT the first NP‑complete problem.
Randomized algorithms: Las Vegas algorithms are always correct with expected runtime (e.g., $\mathbb{E}[T(n)]=O(n\log n)$ for randomized quicksort); Monte Carlo algorithms run in fixed time with error ≤½, which can be reduced by amplification to $(\tfrac12)^k$ after $k$ repetitions.
Bin packing: the decision version is NP‑complete and the optimization version NP‑hard; heuristics like First Fit Decreasing guarantee $\mathrm{FFD}(I)\le\frac{11}{9}\mathrm{OPT}(I)+\frac{6}{9}$ .
Together they illustrate three core CS themes: proving hardness via reductions, leveraging randomness for efficient algorithm design, and using heuristics/approximation to tackle intractable optimization problems.

Research more with Coursify