Randomized algorithms and expected cost

A Las Vegas algorithm always returns the correct answer whenever it terminates, with random running time; a stated finite expected runtime also implies termination with probability one in the usual nonnegative cost model. A Monte Carlo algorithm may return an incorrect answer with a specified bounded probability, often within a fixed time budget. These labels are descriptions of guarantees, not of particular programming syntax. Randomized quicksort with ordinary correct partitioning is Las Vegas: every pivot sequence produces a valid sorted order.

Assume distinct keys and choose each recursive pivot uniformly from that subarray. For each fixed input, the random choices determine the comparison count. A poor sequence can repeatedly choose an extreme key and take quadratic time, but the expected count is O(n log n). The quantifier order matters: each fixed input receives a good expectation over fresh choices. An adaptive adversary that can observe and influence future pivots requires a separate model; the fixed-input proof does not automatically cover it.

Two ranked keys i and j are compared exactly when one of them is the first pivot selected among ranks i through j. If an interior key is selected first, it separates them into different subproblems before they can meet. If an endpoint is first, its partition step compares the pair. Uniform pivot selection makes every rank in that interval equally likely to be the first selected, so the probability is two divided by the interval's number of ranks.

Summing these probabilities yields at most a constant times n times the harmonic sum, which grows logarithmically. More precisely, the count is 2(n+1)Hₙ−4n for the standard partition model comparing a pivot once with each other key in its subarray. This is an expectation of comparisons, not a universal exact runtime: swaps, recursion management, duplicate handling, and memory behavior require their own accounting. Distinct keys avoid a duplicate-partitioning ambiguity rather than being an irrelevant cosmetic assumption.

A nonnegative cost variable satisfies Markov's inequality: the probability it exceeds t times its mean is at most one divided by t for positive t. That bound is useful but weak. An expected logarithmic factor does not by itself establish concentration around the mean or a tiny failure probability. Stronger quicksort tail analyses use additional structure. Similarly, an unbiased estimator can occasionally be far from its expectation; controlling variance or a tail probability supplies information that unbiasedness alone lacks.

Independent repetition can reduce a Monte Carlo error only when the decision rule and error type justify it. If a one-sided test misses a witness with probability at most one half per independent run, accepting any found witness leaves a miss probability at most two to the minus number of runs. Reusing correlated randomness invalidates that multiplication. In implementation, pseudorandom generators approximate the algorithmic source of randomness under their intended assumptions; neither an animation nor a single benchmark establishes the formal distributional guarantee.