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

Machine Learning Basics

Machine learning is an AI subfield that creates models to learn patterns from data and generalize to unseen examples, following a pipeline from data collection to deployment.

Three main paradigms: supervised (labeled data), unsupervised (structure discovery), and reinforcement learning (trial‑and‑error with rewards).
High‑quality data, feature engineering, and proper train/validation/test splits are essential for performance.
Overfitting (high training accuracy, poor validation) and underfitting (low performance) are identified via loss curves and bias‑variance trade‑off.
Start with simple baseline algorithms (linear/logistic regression, trees, forests) before advancing to complex models.

The Banker's Algorithm: Deadlock Avoidance in Operating Systems

The Banker's Algorithm is a deadlock‑avoidance method that keeps a system in a safe state by checking each resource request against the maximum declared needs of processes.

Maintains Available, Max, Allocation, and Need matrices, where $\text{Need}[i][j]=\text{Max}[i][j]-\text{Allocation}[i][j]$ .
The Safety Algorithm uses vectors Work and Finish to find an execution order; if all processes finish, the state is safe.
The Resource‑Request Algorithm simulates allocation, runs the safety check, and commits only if the resulting state remains safe.
Time complexity of the safety check is $O(m \times n^{2})$ .
In practice the algorithm is rarely used because processes must predeclare maximum needs and the algorithm’s overhead is high.

Browse all research articles