Randomized algorithms use random numbers as part of their logic. They have become essential tools in modern software engineering because they often provide simpler implementations, faster average‑case performance, or better scalability compared to deterministic counterparts.
What are Randomized Algorithms?
A randomized algorithm is an algorithm that makes random choices during execution. The outcome—whether it be running time, output, or both—depends on the sequence of random values drawn from a probability distribution.
Why Use Randomization?
- Simplifies complex logic (e.g., quicksort pivot selection).
- Improves expected running time on average inputs.
- Provides probabilistic guarantees where deterministic solutions are unknown.
- Often reduces memory usage or code complexity.
Common Types of Randomized Algorithms
- Monte Carlo algorithms – bounded error probability.
- Las Vegas algorithms – always correct, random running time.
- Random Sampling – reduce problem size while preserving properties.
- Random Walks & Markov Chain Monte Carlo – used for approximation.
Monte Carlo vs Las Vegas
Monte Carlo algorithms trade correctness for speed: they may return an incorrect answer with a small probability. Las Vegas algorithms guarantee correct output but their execution time is a random variable.
Randomness is a resource, not a bug.
Key Example: Randomized QuickSort
Algorithm Overview
QuickSort is a classic divide‑and‑conquer sort. By selecting the pivot randomly, the algorithm avoids the worst‑case O(n2) scenario that occurs when the pivot is consistently chosen poorly.
def randomized_quicksort(arr):
import random
if len(arr) <= 1:
return arr
# Randomly pick a pivot
pivot = random.choice(arr)
less = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
greater = [x for x in arr if x > pivot]
return randomized_quicksort(less) + equal + randomized_quicksort(greater)// Randomized QuickSort in C++
#include <bits/stdc++.h>
using namespace std;
vector<int> randomized_quicksort(vector<int> a) {
if (a.size() <= 1) return a;
// Choose a random pivot
int pivot = a[rand() % a.size()];
vector<int> less, equal, greater;
for (int x : a) {
if (x < pivot) less.push_back(x);
else if (x == pivot) equal.push_back(x);
else greater.push_back(x);
}
vector<int> sorted;
auto left = randomized_quicksort(less);
auto right = randomized_quicksort(greater);
sorted.insert(sorted.end(), left.begin(), left.end());
sorted.insert(sorted.end(), equal.begin(), equal.end());
sorted.insert(sorted.end(), right.begin(), right.end());
return sorted;
}Key Example: Karger's Randomized Min‑Cut
Algorithm Overview
Karger's algorithm repeatedly contracts random edges of a graph. Each contraction reduces the number of vertices by one while preserving the global minimum cut with a certain probability. Repeating the process increases confidence.
// Karger's Min‑Cut (simplified) in C++
#include <bits/stdc++.h>
using namespace std;
int karger_min_cut(vector<vector<int>>& adj) {
// adj[u] contains list of vertices adjacent to u
int n = adj.size();
while (n > 2) {
// pick a random edge (u,v)
int u = rand() % n;
if (adj[u].empty()) continue;
int v = adj[u][rand() % adj[u].size()];
// merge v into u
for (int w : adj[v]) {
if (w != u) adj[u].push_back(w);
// replace v with u in neighbor lists
auto& list = adj[w];
replace(list.begin(), list.end(), v, u);
}
// remove self‑loops
adj[u].erase(remove(adj[u].begin(), adj[u].end(), u), adj[u].end());
// delete vertex v
adj.erase(adj.begin() + v);
--n;
}
// The remaining edges represent a cut
return adj[0].size();
}| Algorithm | Deterministic Complexity | Randomized Expected Complexity | Error Probability |
|---|---|---|---|
| QuickSort | O(n log n) worst‑case | O(n log n) expected | 0 (Las Vegas) |
| Karger's Min‑Cut | O(n²) (deterministic) | O(n²) expected | ≤ 1/n² per trial (Monte Carlo) |
| Monte Carlo Primality Test (Miller‑Rabin) | O(log³ n) deterministic (AKS) | O(k·log³ n) expected | ≤ 4⁻ᵏ per run |
os.urandom() in Python) to avoid patterns.Q: Can I replace a deterministic algorithm with a randomized one without affecting correctness?
A: Randomized algorithms are either Monte Carlo (allow a bounded error probability) or Las Vegas (always correct but runtime is random). You must ensure the error model matches your requirements before substituting.
Q: How do I test a randomized algorithm?
A: Run the algorithm many times with different seeds, use statistical tests to verify expected behavior, and optionally fix a seed for reproducible unit tests.
Q: Is a random seed needed for every execution?
A: Not always. For debugging, a fixed seed improves repeatability. In production, seeding from high‑entropy sources improves distribution quality.
Q. Which of the following statements about Karger's Min‑Cut algorithm is true?
- It always finds the minimum cut in linear time.
- Its runtime is deterministic.
- It succeeds with probability at least 1/|V|².
- It requires sorting the edges.
Answer: It succeeds with probability at least 1/|V|².
Karger's algorithm contracts random edges; the probability of preserving the true min‑cut in a single run is at least 1/(|V| choose 2) ≥ 1/|V|².
Q. What distinguishes a Las Vegas algorithm from a Monte Carlo algorithm?
- Las Vegas algorithms may produce incorrect results.
- Monte Carlo algorithms always run in the same time.
- Las Vegas algorithms always produce the correct result, but their running time is random.
- Monte Carlo algorithms never use random numbers.
Answer: Las Vegas algorithms always produce the correct result, but their running time is random.
Las Vegas guarantees correctness; only the execution time varies. Monte Carlo trades correctness for bounded error probability.