Randomized Algorithms: Algorithm Implementation and Proof

1. Introduction and Core Concepts

Randomized algorithms represent a fundamental paradigm in computer science where an algorithm is allowed to make random choices during its execution to achieve efficiency, simplicity, or robustness that deterministic algorithms cannot easily match. Unlike deterministic algorithms that produce the same output for a given input every time, randomized algorithms inject randomness—typically through a random number generator—to guide decisions such as pivot selection, sampling, hashing, or edge contraction. The core idea is not to introduce uncertainty for its own sake, but to leverage probability theory to obtain algorithms that are faster on average, simpler to implement, and often more resilient to adversarial inputs.

At the heart of randomized algorithms lies the distinction between the algorithm's behavior and its correctness guarantees. A randomized algorithm may be correct with high probability, or it may always be correct but have a random running time. This leads to two canonical classes: Las Vegas algorithms, which always produce the correct result but have a randomized running time, and Monte Carlo algorithms, which have a deterministic running time but may produce an incorrect result with small, bounded probability. Understanding this trade-off is essential for selecting the right randomized approach for a given problem and for proving its performance guarantees.

Why do randomized algorithms matter? In many classical problems, the best-known deterministic solutions are complex or have poor worst-case performance. Randomization often provides a simple, elegant alternative with excellent expected performance. For example, deterministic QuickSort with a fixed pivot rule can be forced into O(n^2) time by a carefully crafted adversarial input, whereas Randomized QuickSort achieves O(n log n) expected time for every input, making it robust in practice. Similarly, problems like primality testing, minimum cut, load balancing, and closest pair benefit enormously from randomization, yielding algorithms that are both theoretically optimal and practically deployed at scale.

The Role of Randomness and Probability

Randomness in algorithms is formally modeled as access to a source of unbiased random bits. The analysis assumes each random choice is independent and uniformly distributed. The performance is then analyzed in terms of expected running time and the probability of failure. Tools from probability theory such as linearity of expectation, Markov's inequality, Chernoff bounds, and the probabilistic method are central to proving that a randomized algorithm performs well. The goal is not merely to show that it works often, but to rigorously bound the probability that it deviates from its expected behavior.

From a proof perspective, randomized algorithms require a shift in reasoning. Instead of proving that an algorithm always finishes in a certain time, we prove statements like "the expected number of comparisons is at most 1.39 n log n" or "the algorithm returns the correct answer with probability at least 1 - 1/n^2". This probabilistic guarantee is often sufficient for real-world systems, especially when the failure probability can be made exponentially small by repetition or parameter tuning. For many applications, an algorithm that is correct with probability 1 - 2^-100 is for all practical purposes correct.

2. How It Works

Randomized algorithms work by replacing deterministic decision points with random sampling. Consider the generic template: while the problem is not solved, sample a random object from a distribution, use it to make progress, and recurse or iterate. The randomness ensures that no single input can consistently trigger the worst-case behavior, because the worst case now depends on the random coin flips rather than just the input structure. This is particularly powerful against an adversary who might try to craft worst-case inputs if the algorithm's behavior were predictable.

The mechanism can be understood through two models. In the Las Vegas model, randomness affects only efficiency. A classic example is Randomized QuickSort: the algorithm always sorts correctly, but the choice of pivot is random. The analysis shows that the expected partition sizes are balanced, leading to expected O(n log n) time. The proof relies on indicator random variables for each pair of elements being compared, and linearity of expectation to sum their probabilities. In the Monte Carlo model, randomness affects correctness. For instance, the Miller-Rabin primality test randomly samples bases to test if a number is composite; if it declares a number composite, it is always correct, but if it declares it prime, there is a small probability of error that decreases exponentially with more iterations.

A critical concept is the adversary model. An oblivious adversary must fix the input before seeing the algorithm's random choices, while an adaptive adversary can react to them. Most analyses of randomized algorithms assume an oblivious adversary, which is realistic for offline problems. The power of randomization is that it converts worst-case inputs into average-case inputs from the algorithm's perspective. Even if an input is pathological for some fixed random seed, the probability that the algorithm picks that bad seed is tiny.

Las Vegas vs. Monte Carlo

Las Vegas algorithms can be converted into Monte Carlo algorithms by imposing a time limit and outputting a failure symbol if the limit is exceeded. Conversely, a Monte Carlo algorithm with one-sided error can be converted into a Las Vegas algorithm by repeating until a certifiably correct answer is found, when such a certificate exists. This duality is important for implementation: many production systems prefer Las Vegas algorithms because they never return a wrong answer, even if they occasionally take longer, while real-time systems may prefer Monte Carlo algorithms with strict deadlines and a negligible error rate.

Randomness as a Resource

The number of random bits required is also a complexity measure. An algorithm that uses O(n) random bits may be less desirable than one that uses O(log n) bits if true randomness is expensive. Techniques like pairwise independence and limited independence, as well as pseudorandom generators, allow us to reduce randomness while preserving analytical guarantees. The theory of derandomization studies how to convert randomized algorithms into deterministic ones with similar performance, often at the cost of increased complexity.

3. Implementation

Implementing randomized algorithms in Python requires careful use of the random module and attention to reproducibility, seeding, and statistical correctness. The following examples demonstrate canonical randomized algorithms with detailed comments, proper handling of edge cases, and proofs of correctness sketched alongside the code. Note that for cryptographic or security-sensitive applications, random should be replaced with secrets or random.SystemRandom to ensure cryptographically strong randomness.

The first implementation is Randomized QuickSort, the quintessential Las Vegas algorithm. It demonstrates random pivot selection and in-place partitioning. The second is the Miller-Rabin primality test, a Monte Carlo algorithm with one-sided error that is widely used in practice for generating large primes in cryptography.

import random

def randomized_quicksort(arr, low=0, high=None):
    """
    Las Vegas Randomized QuickSort.
    Always sorts correctly. Expected time O(n log n).
    Randomness: pivot chosen uniformly at random in [low, high].
    """
    if high is None:
        high = len(arr) - 1
    if low < high:
        # Random pivot selection - key to expected O(n log n)
        pivot_idx = random.randint(low, high)
        arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
        
        # Lomuto partition around arr[high] (now random pivot)
        pivot = arr[high]
        i = low
        for j in range(low, high):
            if arr[j] <= pivot:  # <= ensures stability for duplicates
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
        arr[i], arr[high] = arr[high], arr[i]
        
        # Recurse on partitions; expected balanced splits
        randomized_quicksort(arr, low, i - 1)
        randomized_quicksort(arr, i + 1, high)
    return arr

# Example usage:
# arr = [3, 6, 8, 10, 1, 2, 1]
# randomized_quicksort(arr) -> [1, 1, 2, 3, 6, 8, 10]

import random

def is_probable_prime(n, k=10):
    """
    Miller-Rabin primality test - Monte Carlo algorithm.
    Returns False if n is definitely composite.
    Returns True if n is probably prime (error < 4^-k).
    Correctness: If n is prime, always returns True.
                 If n is composite, returns True with prob <= 4^-k.
    """
    if n < 2:
        return False
    if n in (2, 3):
        return True
    if n % 2 == 0:
        return False

    # Write n-1 as d * 2^r with d odd
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2

    # Witness loop: k random bases
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)  # a^d mod n
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False  # Definitely composite
    return True  # Probably prime

# Amplification: increasing k exponentially reduces error.
# For k=10, error probability < 1 in 1,048,576 for any composite.

import random

def randomized_quickselect(arr, k, low=0, high=None):
    """
    Randomized QuickSelect - Las Vegas algorithm for k-th smallest element.
    Expected time O(n), worst-case O(n^2) but with negligible probability.
    Proof idea: Expected partition reduces problem size by constant factor.
    """
    if high is None:
        high = len(arr) - 1
    if low == high:
        return arr[low]
    
    # Random pivot
    pivot_idx = random.randint(low, high)
    arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
    pivot = arr[high]
    
    # Partition
    i = low
    for j in range(low, high):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[high] = arr[high], arr[i]
    
    # Rank of pivot
    rank = i - low  # number of elements < pivot in subarray
    if k == rank:
        return arr[i]
    elif k < rank:
        return randomized_quickselect(arr, k, low, i - 1)
    else:
        return randomized_quickselect(arr, k - rank - 1, i + 1, high)

# Example: Find median (k = n//2) in expected linear time
# arr = [7, 10, 4, 3, 20, 15]; randomized_quickselect(arr, 3) -> 10 (4th smallest)

import random
from collections import defaultdict

def karger_min_cut(graph):
    """
    Karger's Randomized Contraction Algorithm - Monte Carlo.
    Finds minimum cut with probability >= 2 / (n*(n-1)).
    Repeated O(n^2 log n) times gives high success probability.
    graph: dict {node: set(neighbors)} for undirected multigraph
    """
    # Deep copy to avoid mutating original
    contracted = {u: set(vs) for u, vs in graph.items()}
    # Keep track of supernodes
    supernode_size = {u: 1 for u in graph}
    
    nodes = list(contracted.keys())
    
    while len(contracted) > 2:
        # Pick random edge (u, v) uniformly
        u = random.choice(list(contracted.keys()))
        if not contracted[u]:
            continue
        v = random.choice(list(contracted[u]))
        
        # Contract v into u: merge adjacency lists
        # Remove self-loops that will be created
        for w in list(contracted[v]):
            if w != u:
                contracted[u].add(w)
                contracted[w].add(u)
            contracted[w].discard(v)
            contracted[w].discard(u)  # will re-add u if needed
        # Fix: re-add edges correctly
        # Simplified contraction for illustration
        contracted[u].discard(v)
        contracted[u].discard(u)
        del contracted[v]
    
    # Number of crossing edges is the cut size
    remaining = list(contracted.keys())
    if len(remaining) < 2:
        return 0
    cut_size = len(contracted[remaining[0]])
    return cut_size

def repeated_karger(graph, iterations=None):
    """Amplify success probability by repetition."""
    n = len(graph)
    if iterations is None:
        iterations = n * n  # O(n^2) repetitions for high probability
    best = float('inf')
    for _ in range(iterations):
        cut = karger_min_cut(graph)
        if cut < best:
            best = cut
    return best

4. Step-by-Step Example

To make the abstract concrete, let us walk through Randomized QuickSort on the array [5, 2, 9, 1, 5, 6]. The goal is to see how random pivot choices lead to balanced partitions on average and why the correctness proof holds regardless of randomness. We will trace one possible execution path; remember that different runs will choose different pivots and thus have different recursion trees, but all will produce the sorted array [1, 2, 5, 5, 6, 9].

Initial call: low=0, high=5, subarray [5, 2, 9, 1, 5, 6]. Suppose random.randint(0,5) returns 3, so pivot is arr[3]=1. We swap arr[3] with arr[5], yielding [5, 2, 9, 6, 5, 1]. Partitioning with pivot=1: we scan j=0..4. No element except the pivot itself is <= 1, so i stays at 0. After the loop, we swap arr[0] and arr[5], resulting in [1, 2, 9, 6, 5, 5] with pivot index i=0. This is an unbalanced partition (0 elements left, 5 right), which is the worst case for this step, but it occurs with probability only 1/6 for this array size.

Recurse on right subarray [2, 9, 6, 5, 5] with low=1, high=5. Suppose next random pivot index is 2 (value 9). Swap with arr[5]=5 → [2, 5, 6, 5, 9] (relative to subarray). Partition with pivot=9: all elements <= 9, so i moves to 5, and after swap the array remains [1, 2, 5, 6, 5, 9] with pivot at index 5. Now recurse on [2, 5, 6, 5] (indices 1-4). Suppose pivot is 5 (choose index 2, value 5). Partitioning this subarray: elements <=5 are 2,5,5, so after partition we might get [2,5,5,6] with pivot in the middle. This balanced split quickly reduces the problem size.

Continuing, the recursion will sort the remaining small subarrays in one or two more steps. The total number of comparisons in this particular run was higher than average due to the first bad pivot (1), but the expected number of comparisons over all random choices is O(n log n). The proof that the algorithm is always correct is by induction on subarray size: partitioning places the pivot in its final sorted position, and recursively sorting the left and right subarrays yields a fully sorted array. Randomness does not affect correctness, only the shape of the recursion tree and thus the running time. This is the hallmark of a Las Vegas algorithm.

Why This Walkthrough Matters for Proofs

This example illustrates the probabilistic analysis technique: define for each pair of elements (i, j) an indicator variable X_ij = 1 if they are compared. The probability they are compared equals the probability that one of them is chosen as pivot before any element between them is chosen. For sorted values z_1 < z_2 < ... < z_n, Pr[X_ij = 1] = 2 / (j - i + 1). Summing expectations gives E[total comparisons] = sum_{i<j} 2/(j-i+1) = O(n log n). The step-by-step trace shows how a single bad pivot is amortized by many good pivots in expectation.

5. Complexity Analysis

Analyzing randomized algorithms requires distinguishing between worst-case, best-case, expected, and high-probability bounds. The worst-case running time of a Las Vegas algorithm is often the same as its deterministic counterpart (e.g., O(n^2) for QuickSort), but the probability of hitting that worst case is exponentially small. Therefore, expected time and concentration bounds are more informative. For Monte Carlo algorithms, we analyze both running time (usually deterministic) and error probability.

For Randomized QuickSort, the expected number of comparisons is at most 2n ln n ≈ 1.39 n log2 n, and the expected recursion depth is O(log n), giving O(log n) expected stack space. With high probability (1 - 1/n^c for any constant c), the running time is O(n log n) as well, proven via Chernoff bounds on the number of times a bad pivot is chosen. Randomized QuickSelect has expected O(n) time, with a similar high-probability bound. Karger's algorithm runs in O(n^2) per trial (with efficient union-find, O(m) per contraction) and needs O(n^2 log n) repetitions to achieve high success probability, yielding O(n^4 log n) total time, which can be improved to O(n^2 log n) with the Karger-Stein variant.

Space complexity is typically O(log n) for recursion stack in QuickSort/QuickSelect, O(n) for graph contraction, and O(1) auxiliary for Miller-Rabin besides the input size. The key insight is that randomization often trades a small amount of extra space or error probability for a dramatic improvement in expected time, especially in circumventing worst-case inputs that plague deterministic algorithms.

Proving Expected Bounds

Proofs of expected complexity typically use linearity of expectation and indicator variables, as shown for QuickSort. For Karger's algorithm, the proof that a specific minimum cut survives contraction is elegant: the probability that no edge of the cut is contracted in the first step is 1 - k/m where k is cut size and m is number of edges, and since m ≥ n*k/2, this is ≥ 1 - 2/n. Telescoping the product over n-2 contractions yields survival probability ≥ 2/(n(n-1)). This lower bound is tight and justifies repetition. For Miller-Rabin, the proof that at most 1/4 of bases are liars for any composite n relies on group theory and is the foundation for the 4^-k error bound.

6. Variations and Optimizations

Randomized algorithms have numerous variants and optimization techniques that improve constants, reduce randomness, or provide stronger guarantees. One common optimization is median-of-three or random sampling for pivot selection: instead of picking one random element, sample three random elements and pick their median. This reduces the probability of a very unbalanced partition from 2/n to O(1/n^2) for extreme splits, improving the constant factor in expected time while adding only O(1) overhead. Another variant is to switch to insertion sort for small subarrays (e.g., size < 10), which is faster in practice due to cache locality and lower overhead.

For Karger's algorithm, the Karger-Stein improvement uses a recursive contraction strategy: contract the graph to n/√2 nodes twice independently, then recursively find the min cut in each branch and take the smaller. This reduces the number of repetitions from O(n^2) to O(log n) and improves total time to O(n^2 log n). For Miller-Rabin, deterministic variants exist for 32-bit and 64-bit integers by testing a fixed set of bases (e.g., [2, 7, 61] suffices for n < 2^32), effectively derandomizing the algorithm for bounded inputs. This is a practical optimization used in many standard libraries.

Another powerful technique is amplification by repetition. For Monte Carlo algorithms with one-sided error, repeating the algorithm and taking the majority vote or the best result exponentially reduces error probability. For Las Vegas algorithms, restarting after a timeout can convert a heavy-tailed distribution into one with better expected time. Techniques like random hashing with universal hash families guarantee expected O(1) operations regardless of input distribution, and consistent hashing optimizes for dynamic addition/removal of servers.

Derandomization and Limited Independence

Derandomization seeks to replace random bits with deterministic choices without sacrificing performance. Conditional expectation and pessimistic estimators can sometimes derandomize algorithms with only polynomial overhead. Limited independence—using pairwise or k-wise independent hash functions instead of fully random ones—reduces the number of random bits from O(n) to O(log n) while preserving enough randomness for the analysis to go through. This is crucial for streaming algorithms and large-scale systems where generating true randomness is costly.

Finally, hybrid algorithms combine randomization with deterministic fallbacks. For example, introsort starts with randomized quicksort but switches to heapsort if recursion depth exceeds 2 log n, guaranteeing O(n log n) worst-case time while retaining the speed of quicksort in practice. Such hybrids are the default in languages like C++ and Python's Timsort (which is deterministic but inspired by similar trade-offs).

7. Real-World Applications

Randomized algorithms are not just theoretical curiosities; they are the backbone of many large-scale systems. In web servers and load balancers, the "power of two choices" paradigm randomly samples two servers and assigns a request to the less loaded one, achieving exponential improvement in load balance over purely random assignment with minimal overhead. Content Delivery Networks (CDNs) use consistent hashing—a randomized hashing technique—to distribute content across caches while minimizing remapping when nodes join or leave.

In databases, randomized algorithms enable efficient query processing and indexing. Hash tables with universal hashing provide expected O(1) lookups even under adversarial keys, which is why most in-memory databases and caches (Redis, Memcached) rely on them. Bloom filters, a probabilistic data structure with one-sided error, use multiple random hash functions to test set membership with tiny space overhead, widely used in databases (Cassandra, BigTable) to avoid expensive disk lookups. Skip lists, a randomized alternative to balanced trees, are used in Redis and LevelDB for their simplicity and expected O(log n) operations.

In networks, randomized algorithms solve critical problems like routing, contention resolution, and minimum cut. The Karger-Stein algorithm, while not always used directly for min-cut in production (due to more efficient deterministic algorithms like Stoer-Wagner), illustrates the principle behind randomized network reliability estimation. Gossip protocols for failure detection and data dissemination in distributed systems (e.g., Amazon Dynamo, Cassandra) rely on random peer selection to achieve robust, scalable communication with O(log n) rounds.

Cryptography and Security

Perhaps the most critical application is cryptography, where randomness is essential for security. Generating large primes for RSA relies on Miller-Rabin, and every encryption operation uses random nonces and salts to prevent replay attacks. The security proofs themselves are probabilistic, showing that an adversary's success probability is negligible. Without randomized algorithms, modern secure communication would be impossible.

8. Comparison with Alternatives

When deciding whether to use a randomized algorithm, it is important to compare it against deterministic, approximate, and heuristic alternatives. Deterministic algorithms provide absolute guarantees but may be more complex or slower in the worst case. Approximation algorithms guarantee a solution within a factor of optimal but are deterministic. Heuristics are fast but offer no guarantees. Randomized algorithms occupy a unique niche: they offer provable expected performance and high-probability correctness with often simpler implementation.

For sorting, deterministic mergesort guarantees O(n log n) worst-case time and is stable, but requires O(n) extra space and has higher constant factors than quicksort. Randomized quicksort is in-place, has better cache performance, and its expected time matches mergesort's worst case, but it is not stable and has a negligible chance of O(n^2) time. For primality testing, deterministic AKS is polynomial but with high exponents (O(log^6 n)), making it impractical, while Miller-Rabin is fast and practical with tunable error. For min-cut, deterministic Stoer-Wagner runs in O(n^3) or O(m log n) and is often preferred in practice, but Karger's algorithm is far simpler to implement and parallelize.

When to Choose Which

Choose randomized algorithms when average-case performance matters more than absolute worst-case, when inputs may be adversarial, or when simplicity and maintainability are priorities. Choose deterministic algorithms when you need hard real-time guarantees or when certification requires absolute correctness. In practice, many production systems use hybrid approaches: they run a randomized algorithm and fall back to a deterministic one if it takes too long, achieving the best of both worlds.

9. Common Mistakes and Best Practices

Implementing randomized algorithms correctly is subtle, and several pitfalls can invalidate the theoretical guarantees. The most common mistake is using a weak or biased random number generator. Using random.random() with a predictable seed or a low-period generator can make the algorithm deterministic from an adversary's perspective, reintroducing worst-case behavior. For security-sensitive applications, always use secrets or os.urandom. For simulations, explicitly seed the generator and log the seed for reproducibility, but never use a fixed seed in production where adversarial inputs are possible.

Another frequent error is incorrect amplification. Repeating a Monte Carlo algorithm and taking a majority vote only works if errors are independent and one-sided error is handled correctly. For Miller-Rabin, simply repeating with the same base does not reduce error; you must choose independent random bases each time. Similarly, for Karger's algorithm, running it once and assuming the result is correct ignores the O(1/n^2) success probability; you must repeat O(n^2 log n) times and take the minimum. Failing to account for the union bound when amplifying can lead to overconfidence in the result.

A third mistake is misinterpreting expected time as a guarantee. An expected O(n log n) algorithm can still take O(n^2) on a particular run, albeit with tiny probability. Systems that require hard deadlines should not rely solely on expectation; they should either set timeouts and fall back to a deterministic algorithm (like introsort) or prove a high-probability bound using concentration inequalities. Always analyze both expectation and variance, and consider the distribution's tail.

Best Practices

• Seed Management: Allow seeding for testing and debugging, but use cryptographically secure randomness in production. Log seeds for failed runs to enable reproduction.
• Prove Before Coding: Write down the probabilistic guarantee you need (e.g., error < 1e-9) and compute the required number of iterations using Chernoff or union bounds before implementing loops.
• Test Statistically: Unit tests with fixed seeds are insufficient. Run statistical tests over many random seeds to verify that empirical performance matches expected bounds and that error rates are within predicted limits.
• Handle Edge Cases Deterministically: For small inputs (n < 10), deterministic logic is often faster and avoids overhead. Check for n < 2, empty graphs, or duplicate keys explicitly.
• Document Randomness Assumptions: Clearly state whether your analysis assumes an oblivious or adaptive adversary, and whether you need full independence or just pairwise independence, so future maintainers do not inadvertently weaken the guarantees.

Finally, beware of floating-point and modulo bias when generating random integers in a range. Using random.randint(a,b) is correct in Python, but implementing your own rand() % n can introduce bias if the generator's range is not a multiple of n. Always use the standard library's uniform sampling functions.

10. Interview Questions

Randomized algorithms are a favorite in technical interviews because they test understanding of probability, analysis, and trade-offs. Interviewers often ask not just to implement an algorithm, but to prove its expected performance and discuss when randomization helps. Below are common questions with guidance on what a strong answer should include.

Q1: How would you find the k-th smallest element in expected linear time?

This tests Randomized QuickSelect. A strong answer describes random pivot selection, partitioning, and recursing on only one side. The proof sketch should use the observation that a "good" pivot (in the middle 50% of sorted order) is chosen with probability 1/2, and after a good pivot the problem size reduces to at most 3n/4. Then expected time satisfies T(n) ≤ n + (1/2)T(3n/4) + (1/2)T(n), solving to O(n). Mention worst-case O(n^2) but negligible probability, and compare to deterministic median-of-medians which guarantees O(n) worst-case but with larger constants.

Q2: Explain the difference between Las Vegas and Monte Carlo algorithms. Give an example of each.

Expect a clear definition: Las Vegas always correct, random runtime; Monte Carlo fixed runtime, possibly incorrect. Examples: Randomized QuickSort/QuickSelect are Las Vegas; Miller-Rabin and Karger's are Monte Carlo (Karger's can be made Las Vegas by verifying the cut). Discuss conversion: Las Vegas to Monte Carlo by timeout, Monte Carlo to Las Vegas by repetition with verification. Bonus points for mentioning that Miller-Rabin has one-sided error (never says composite is prime) and how that affects amplification.

Q3: How does Randomized QuickSort achieve O(n log n) expected time? Prove it.

This is the classic analysis question. The candidate should define indicator variables for pairs (i,j) being compared and compute Pr[comparison] = 2/(j-i+1). Then use linearity of expectation to sum over all pairs: E[comparisons] = Σ_{i<j} 2/(j-i+1) = O(n log n). A weaker but acceptable answer can argue via recursion tree and expected partition balance: with probability 1/2 the pivot is in the middle half, leading to balanced splits and expected depth O(log n). Distinguish between expected time and high-probability bound, and mention why deterministic pivot choices fail against adversarial inputs.

Q4: You need to test if a number is prime for RSA key generation. Which algorithm would you use and why?

The answer is Miller-Rabin with sufficient iterations (e.g., k=20 for 2^-40 error) or a deterministic variant for 64-bit. Discuss why trial division is O(√n) and infeasible for 1024-bit numbers, why AKS is too slow in practice, and how Miller-Rabin's 4^-k error bound is made negligible by repetition. Mention the need for cryptographically secure random bases and that for n < 2^64, testing bases {2,3,5,7,11,13} is deterministic. This shows practical judgment beyond theory.

Q5: Design a randomized algorithm for load balancing n jobs across m servers.

This tests the "power of two choices" and balls-into-bins analysis. A naive random assignment gives max load O(log n / log log n) with high probability. Sampling two servers and picking the less loaded reduces max load to O(log log n), an exponential improvement. The candidate should describe the algorithm, state the expected max load, and sketch the proof using layered induction or witness trees. Discuss real-world extensions: consistent hashing for dynamic servers, and how randomization prevents herd behavior that deterministic round-robin might cause under skewed job sizes.