Quick sort randomization — expected O(n log n): Worked examples

Before we start, one reminder of the single formula everything below uses. From the parent note:

The key numbers here are the gap $d = j - i$ (how far apart two elements sit in sorted order) and the resulting probability $\frac{2}{d + 1}$ . Notice: the probability depends only on the gap, never on the actual values or where the elements started. Keep that in your pocket.

The scenario matrix

Every question this topic can throw at you falls into one of these cells. The worked examples below are labelled with the cell (C1–C9) they cover.

Cell	Scenario class	What's tricky about it	Example
C1	Smallest non-trivial array ( $n = 2, 3$ )	Are adjacent elements always compared?	Ex 1
C2	Full expected count for small $n$	Grouping pairs by gap	Ex 2
C3	Gap extremes — adjacent ( $d = 1$ ) vs far ( $d$ max)	$Pr = 1$ vs $Pr$ tiny	Ex 3
C4	"Adversary" sorted / reverse-sorted input	Does input order change the answer?	Ex 4
C5	Degenerate: $n = 1$ and $n = 0$	Zero comparisons, base case	Ex 5
C6	Duplicates / equal keys	Does "sorted order" still make sense?	Ex 6
C7	Limiting behaviour (large $n$ )	$H_{n} \to ln n$ , ratio to $n ln n$	Ex 7
C8	Real-world word problem	Translate a story into the formula	Ex 8
C9	Exam twist — conditional / "given first pivot"	Reasoning under a condition	Ex 9

Worked examples

Ex 1 — smallest non-trivial arrays (Cell C1)

Worked example

$n = 2$ and $n = 3$ : how many comparisons on average? Compute $E [X]$ for $n = 2$ , then for $n = 3$ .

Forecast: For two elements, guess: is the number of comparisons random at all, or is it fixed? For three, will it be a nice fraction or an integer?

Step 1 — $n = 2$ : list the pairs. Only one pair exists: $(z_{1}, z_{2})$ , gap $d = 2 - 1 = 1$ . Why this step? $E [X]$ is a sum over pairs $i < j$ ; with two elements there is exactly one pair to sum.

Step 2 — apply the formula. $Pr [z_{1} \leftrightarrow z_{2}] = \frac{2}{d + 1} = \frac{2}{2} = 1$ . So $E [X] = 1$ . Why this step? Gap-1 (adjacent) elements are compared with probability $1$ — one of them must become the pivot before they can be split apart, and comparing against the pivot is unavoidable.

Step 3 — $n = 3$ : list all pairs. $(z_{1}, z_{2})$ gap 1, $(z_{2}, z_{3})$ gap 1, $(z_{1}, z_{3})$ gap 2. Why this step? With three elements there are $(2 3) = 3$ pairs; we need all of them.

Step 4 — sum the probabilities. $E [X] = (1, 2) \frac{2}{2} + (2, 3) \frac{2}{2} + (1, 3) \frac{2}{3} = 1 + 1 + \frac{2}{3} = \frac{8}{3} \approx 2.667$ Why this step? Linearity of Expectation lets us add each pair's probability directly — no independence needed, which is the whole reason this method is so clean.

Verify: For $n = 2$ , sorting two elements always takes exactly one comparison, no matter the pivot — so $E [X] = 1$ is not just an average, it's a certainty. For $n = 3$ : minimum possible is 2 comparisons (if the middle element $z_{2}$ is picked first, it splits cleanly, then each side of size 1 costs 0 more... but partitioning still compares $z_{2}$ against both others = 2). If an extreme is picked first (prob $2/3$ ), you get 3 comparisons. So $E [X] = \frac{1}{3} (2) + \frac{2}{3} (3) = \frac{2 + 6}{3} = \frac{8}{3}$ . ✅ Matches.

Ex 2 — the full count for $n = 5$ (Cell C2)

Worked example Expected comparisons for a 5-element array

Compute $E [X]$ for $n = 5$ by grouping pairs by gap.

Forecast: There are $(2 5) = 10$ pairs. Guess whether the answer is closer to 5, 7, or 10.

Step 1 — count how many pairs have each gap $d$ . In a line of 5 positions, the number of pairs with gap $d$ is $5 - d$ :

$d = 1$ : 4 pairs
$d = 2$ : 3 pairs
$d = 3$ : 2 pairs
$d = 4$ : 1 pair

Why this step? The probability $\frac{2}{d + 1}$ depends only on the gap, so we batch pairs by gap and multiply by how many share that gap — far faster than listing all 10.

Step 2 — multiply each group by its probability. $E [X] = 4 \cdot \frac{2}{2} + 3 \cdot \frac{2}{3} + 2 \cdot \frac{2}{4} + 1 \cdot \frac{2}{5}$ Why this step? Each of the $5 - d$ pairs at gap $d$ contributes the same $\frac{2}{d + 1}$ ; Linearity of Expectation says just add them.

Step 3 — arithmetic. $= 4 (1) + 3 (\frac{2}{3}) + 2 (\frac{1}{2}) + \frac{2}{5} = 4 + 2 + 1 + 0.4 = 7.4$

Verify: Two independent sanity checks. (a) Direct enumeration: literally adding all 10 pair-probabilities $\frac{2}{d + 1}$ one by one also gives $7.4$ (done in Linearity of Expectation style). (b) Below the parent's bound: the parent note derived the loose bound $E [X] < 2 (n - 1) H_{n}$ by replacing each $\frac{2}{k + 1}$ with the strictly larger $\frac{2}{k}$ and extending the inner sum to $H_{n}$ . With $H_{5} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} = \frac{137}{60} \approx 2.2833$ , that bound is $2 (4) (2.2833) = 18.27$ , and indeed $7.4 < 18.27$ ✅. The bound is deliberately loose — Ex 7 upgrades it to a tight closed form. Also $7.4$ sits between 5 and 10 — reasonable for 10 pairs where far-apart ones rarely meet.

Ex 3 — gap extremes side by side (Cell C3)

Worked example Adjacent vs. far-apart in one array of

$n = 9$ Compare $Pr [z_{1} \leftrightarrow z_{2}]$ (adjacent) against $Pr [z_{1} \leftrightarrow z_{9}]$ (the two extremes).

Forecast: One of these is a guarantee and one is rare. Which is which, and roughly how rare?

Step 1 — adjacent pair, gap $d = 1$ . $Pr [z_{1} \leftrightarrow z_{2}] = \frac{2}{1 + 1} = 1$ . Why this step? The figure below draws all nine sorted positions $z_{1}, \dots, z_{9}$ as black dots on a line. The accent-red short arrow above marks the adjacent pair $z_{1}, z_{2}$ (leftmost two dots), which has nothing between them — so the only way to separate them into different subarrays would be a pivot of value strictly between $z_{1}$ and $z_{2}$ , which does not exist. Before they can ever part, one of the two must itself be chosen as pivot, forcing the comparison. Probability 1. Contrast this with the extremes $z_{1}$ and $z_{9}$ : the red double-arrow below spans a wide gap with seven black dots ( $z_{2}, \dots, z_{8}$ ) sitting between them, any one of which can wedge in as a pivot first.

Figure: Nine sorted positions as black dots. Red short arrow (top) = adjacent pair $z_{1}, z_{2}$ , gap 1, probability 1. Red wide arrow (bottom) = extreme pair $z_{1}, z_{9}$ , gap 8, probability 2/9 — the seven middle dots between them can each split the pair apart.

Step 2 — extreme pair, gap $d = 8$ . $Pr [z_{1} \leftrightarrow z_{9}] = \frac{2}{8 + 1} = \frac{2}{9} \approx 0.2222$ . Why this step? Now there are 7 middle elements $z_{2}, \dots, z_{8}$ (the black dots between the red endpoints in the figure). If any of them is chosen as a pivot before $z_{1}$ or $z_{9}$ , the two extremes get thrown into opposite partitions and never meet. Only 2 of the 9 candidates ( $z_{1}$ or $z_{9}$ ) are "good".

Step 3 — ratio. The adjacent pair is $\frac{1}{2/9} = 4.5 \times$ more likely to be compared than the extreme pair.

Verify: As the gap grows, $\frac{2}{d + 1} \to 0$ — far-apart elements almost never meet, which is exactly why the total stays $O (n lo g n)$ and not $O (n^{2})$ : most of the $(2 n)$ pairs contribute tiny probabilities. ✅

Ex 4 — the "adversary" input (Cell C4)

Worked example Sorted

[1,2,3,4,5] vs. shuffled — does $E [X]$ change? Deterministic last-element-pivot quicksort dies on sorted input ( $O (n^{2})$ ). What is $E [X]$ for randomized quicksort on the same sorted input [1,2,3,4,5]?

Forecast: Will sorted input give a bigger $E [X]$ than random input, or exactly the same?

Step 1 — identify the sorted order. The input [1,2,3,4,5] is already sorted, so $z_{1} = 1, \dots, z_{5} = 5$ . Why this step? The formula is stated in terms of the sorted positions $z_{i}$ , so we must map values to positions first.

Step 2 — realise the formula never mentions input order. $E [X] = \sum_{i < j} \frac{2}{j - i + 1}$ depends only on $n$ and the gaps, not on how the array was arranged when it arrived. Why this step? Random pivoting makes each pivot's rank uniformly random regardless of layout — this is the entire point of randomization (it "breaks the link between input order and pivot rank", per the parent note). The adversary's carefully sorted array is now no different from a shuffled one.

Step 3 — reuse Ex 2's computation. Same $n = 5$ , so $E [X] = 7.4$ .

Verify: Deterministic last-pivot on this sorted input compares the pivot against every remaining element each level: $4 + 3 + 2 + 1 = 10$ comparisons (its worst case). Randomized expects only $7.4$ — strictly less, and crucially the $7.4$ holds for every input, including this "adversarial" one. Randomization removed the bad input, not the bad luck. ✅ (See Quicksort (deterministic) for the version that actually suffers here, and Las Vegas vs Monte Carlo algorithms — this is a Las Vegas algorithm: always correct, running time random.)

Ex 5 — degenerate inputs $n = 0$ and $n = 1$ (Cell C5)

Worked example The base cases

What is $E [X]$ for an empty array ( $n = 0$ ) and a single-element array ( $n = 1$ )?

Forecast: Zero, one, or "undefined"?

Step 1 — $n = 1$ : count the pairs. The sum $\sum_{i < j}$ needs two distinct indices; with one element there is no pair $i < j$ . Why this step? An empty sum is $0$ by convention — nothing to add.

Step 2 — $n = 0$ : same reasoning. No elements, no pairs, $E [X] = 0$ . Why this step? This confirms the recursion's base case: QUICKSORT(A, lo, hi) does nothing when lo >= hi, i.e. subarrays of size $\leq 1$ trigger zero comparisons.

Verify: A list of length 0 or 1 is already sorted, so of course no comparisons are needed. The formula gracefully returns $0$ instead of dividing by anything dangerous — no degenerate blow-up. ✅ Also: $2 (n - 1) H_{n}$ at $n = 1$ gives $2 (0) H_{1} = 0$ , consistent.

Ex 6 — duplicate keys (Cell C6)

Worked example Does the analysis survive equal elements?

[7,7,7] Estimate the comparison count for three equal keys, and explain whether the sorted-order labelling still makes sense.

Forecast: Do duplicates break the " $z_{1} < z_{2} < z_{3}$ " strict-inequality setup?

Step 1 — break ties by original position. Equal keys can't be ordered by value, so we impose a tie-broken total order written $⪯$ : for two equal keys, the one at the smaller array index comes first. Under this rule [7,7,7] becomes $z_{1}, z_{2}, z_{3}$ with $z_{1}$ before $z_{2}$ before $z_{3}$ . The symbol $⪯$ is just " $<$ " extended to also order equal values by index, so every pair has a definite "earlier" and "later". Why this step? The proof only needs a fixed total order so that "the first member of $Z_{ij}$ chosen as a pivot" (see the $Z_{ij}$ definition above) is well-defined. Tie-breaking by index supplies one, and the formula's upper bound still applies.

Step 2 — apply the $n = 3$ result as an upper bound. With the tie-broken order, the same structure as Ex 1 ( $n = 3$ ) gives $E [X] \leq \frac{8}{3} \approx 2.667$ . Why this step? Any real partitioning of equal keys does at most as many comparisons as the distinct-key analysis predicts (a good three-way partition on equal keys can do even fewer).

Verify: In practice, a naive two-way partition on all-equal input compares the pivot against every other element every level. For $n = 3$ that's exactly $2$ comparisons (pivot vs. two others, one level, since both go to the same side). $2 \leq 2.667$ ✅ — the bound holds. The moral: duplicates never make the expected comparison count exceed the distinct-key formula.

Ex 7 — limiting behaviour for large $n$ (Cell C7)

Worked example How does

$E [X]$ grow, and how tight is the constant? Estimate $E [X]$ for $n = 1000$ and find the ratio $\frac{E [ X ]}{n l n n}$ .

Forecast: Guess the ratio: is it near $0.5$ , $1$ , or $2$ ?

Step 1 — set up the double sum and substitute $k = j - i$ . Start from $E [X] = \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} \frac{2}{j - i + 1} .$ Fix $i$ and let $k = j - i$ be the gap. As $j$ runs from $i + 1$ up to $n$ , the gap $k$ runs from $1$ up to $n - i$ , and the term becomes $\frac{2}{k + 1}$ : $E [X] = \sum_{i = 1}^{n - 1} \sum_{k = 1}^{n - i} \frac{2}{k + 1} .$ Why this step? Rewriting in terms of the gap $k$ makes the summand depend on $k$ alone — the inner term no longer mentions $i$ , which is what lets us swap the order of summation next.

Step 2 — swap the summation order (the counting argument). We want to sum over $k$ on the outside. For a fixed gap $k$ , which values of $i$ produce that gap? The condition is $k \leq n - i$ , i.e. $i \leq n - k$ , and $i \geq 1$ . So $i$ ranges over $1, 2, \dots, n - k$ — exactly $n - k$ values of $i$ . Each of those contributes the same term $\frac{2}{k + 1}$ , so summing over them multiplies by $n - k$ : $E [X] = \sum_{k = 1}^{n - 1} (n - k) \frac{2}{k + 1} .$ Why this step? This is the missing counting step: "how many $(i, k)$ pairs share a given gap $k$ ?" The answer $n - k$ is exactly the number of pairs of positions that are $k$ apart in a line of $n$ — the same count we used in Ex 2 when we said " $5 - d$ pairs at gap $d$ ".

Step 3 — split the fraction and evaluate to a closed form. Write $\frac{n - k}{k + 1} = \frac{( n + 1 ) - ( k + 1 )}{k + 1} = \frac{n + 1}{k + 1} - 1$ . Summing the " $- 1$ " over $k = 1$ to $n - 1$ gives $- (n - 1)$ ; summing $\frac{n + 1}{k + 1}$ gives $2 (n + 1) (H_{n} - 1)$ (the shifted harmonic sum $\sum_{k = 1}^{n - 1} \frac{1}{k + 1} = H_{n} - 1$ ). Combining and simplifying yields the exact identity $E [X] = 2 (n + 1) H_{n} - 4 n$ Why this step? The parent's bound $2 (n - 1) H_{n}$ came from rounding up $\frac{2}{k + 1} \to \frac{2}{k}$ ; here we keep the exact $\frac{2}{k + 1}$ and evaluate honestly, so we get an equality. Both are $O (n lo g n)$ — but the boxed form is exact and lets us read off the true constant. (This identity is machine-checked against the raw double sum in the verifier.)

Step 4 — plug $n = 1000$ using $H_{n} \approx ln n + γ$ . From the harmonic-number definition, $H_{1000} \approx ln 1000 + 0.5772 = 6.9078 + 0.5772 = 7.4850$ (the $\frac{1}{2 n} = 0.0005$ correction is negligible here). Then $E [X] \approx 2 (1001) (7.4850) - 4000 = 14985.0 - 4000 = 10985.$ Why this step? Concrete numbers make "asymptotic" tangible.

Step 5 — compute the ratio $\frac{E [ X ]}{n l n n}$ . $n ln n = 1000 \times 6.9078 = 6907.8$ , so $\frac{E [ X ]}{n l n n} \approx \frac{10985}{6907.8} \approx 1.59.$ Why this step? The leading term of $E [X]$ is $2 (n + 1) H_{n} \sim 2 n ln n$ , so the ratio should approach $2$ ; getting $1.59$ at $n = 1000$ shows it is climbing toward $2$ slowly (the slowness is the $ln n$ 's doing).

Verify: $2 (n + 1) H_{n} - 4 n \sim 2 n ln n$ , so dividing by $n ln n$ should tend to $2$ . At $n = 1000$ we get $1.59$ — below $2$ but climbing, exactly as the slow $ln n$ growth predicts ✅. The verifier also confirms the boxed identity equals the raw double sum at $n = 10$ and $n = 1000$ . Compare Merge Sort, which does $\approx n lo g_{2} n \approx 9966$ comparisons here — same $O (n lo g n)$ class, different constant.

Ex 8 — real-world word problem (Cell C8)

Worked example Sorting exam scores

A teacher randomized-quicksorts $50$ exam scores. Estimate the average number of score comparisons the algorithm performs.

Forecast: Closer to $50$ , $250$ , or $1250$ ?

Step 1 — translate the story into symbols. "50 scores" $\Rightarrow n = 50$ . "Average number of comparisons" $\Rightarrow E [X]$ . Any tied scores are handled by the tie-broken order of Ex 6, so the formula still applies. Why this step? Word problems must be mapped to symbols before any formula runs; misidentifying $n$ is the classic error.

Step 2 — approximate $H_{50}$ with its correction term. From the harmonic-number definition, the sharper estimate is $H_{n} \approx ln n + γ + \frac{1}{2 n}$ . Here the extra term is $\frac{1}{2 \cdot 50} = \frac{1}{100} = 0.01$ , which matters at this modest size: $H_{50} \approx ln 50 + 0.5772 + 0.01 = 3.9120 + 0.5772 + 0.01 = 4.4992 \approx 4.499.$ Why this step? We include $\frac{1}{2 n}$ because at $n = 50$ dropping it would cost about $0.01$ in $H_{n}$ and roughly a whole comparison in the final answer — the correction earns its place. (The true value $H_{50} = 4.4992$ confirms the estimate is essentially exact.)

Step 3 — apply the exact closed form from Ex 7. $E [X] = 2 (n + 1) H_{n} - 4 n = 2 (51) (4.499) - 200 = 458.9 - 200 = 258.9 \approx 259$ . Why this step? We reuse the boxed identity rather than the loose bound, so the estimate is tight.

Step 4 — interpret. On average about 259 comparisons to sort 50 scores.

Verify: Cross-check against the parent's loose bound $2 (n - 1) H_{n} = 2 (49) (4.499) = 440.9$ : our $259 < 441$ ✅. And $259$ sits near the $250$ forecast bucket ✅. A naive $O (n^{2})$ scheme would risk $(2 50) = 1225$ comparisons, so randomization keeps us near $259$ instead — units check out (both sides are counts of comparisons).

Ex 9 — exam twist: conditional probability (Cell C9)

Worked example "Given the first pivot of the whole array is

$z_{5}$ , are $z_{1}$ and $z_{9}$ ever compared?" ( $n = 9$ ) Reason about $z_{1} \leftrightarrow z_{9}$ conditioned on $z_{5}$ being the very first pivot chosen for the entire array.

Forecast: Is the conditional probability $0$ , $\frac{2}{9}$ , or something in between?

Step 1 — see what picking $z_{5}$ first does. $z_{5}$ splits everything into a left subarray ${z_{1}, \dots, z_{4}}$ and a right subarray ${z_{6}, \dots, z_{9}}$ . Why this step? The first pivot partitions by rank; anything smaller than $z_{5}$ goes left, anything larger goes right. So $z_{1}$ lands left and $z_{9}$ lands right.

Step 2 — check whether they can ever meet again. Once separated into different subarrays, quicksort never compares elements across the split. So $Pr [z_{1} \leftrightarrow z_{9} ∣ first pivot = z_{5}] = 0$ . Why this step? This is precisely the "middle pivot" losing case from the parent's derivation, but here the conditioning forces the middle pivot to be chosen first.

Step 3 — reconcile with the unconditional $\frac{2}{9}$ . The unconditional $Pr = \frac{2}{9}$ averages over which member of $Z_{19} = {z_{1}, \dots, z_{9}}$ is picked first. $z_{5}$ is one of the 7 "bad" middles; conditioning on a bad middle gives $0$ . Conditioning on $z_{1}$ or $z_{9}$ first would give $1$ .

Verify: Check the average matches: each of the 9 members of $Z_{19}$ is equally likely ( $\frac{1}{9}$ ) to be "first pivot among $Z_{19}$ ". The 2 good ones give $1$ , the 7 bad give $0$ : $\frac{1}{9} (2 \cdot 1 + 7 \cdot 0) = \frac{2}{9}$ ✅ — exactly the unconditional probability. The condition just fixed one of the coin flips.

Active recall

Recall Which matrix cell does each fact hit? (open after attempting)

Adjacent elements ( $d = 1$ ) are compared with probability… ::: exactly $1$ (Cell C3/C1). $E [X]$ for $n = 5$ … ::: $7.4$ comparisons (Cell C2). Does sorted input raise $E [X]$ for randomized quicksort? ::: No — the formula ignores input order; still $7.4$ for $n = 5$ (Cell C4). $E [X]$ for $n = 0$ or $n = 1$ … ::: $0$ (empty sum, Cell C5). Do duplicate keys break the analysis? ::: No — tie-break by index; the distinct-key formula is an upper bound (Cell C6). Exact closed form for $E [X]$ ? ::: $2 (n + 1) H_{n} - 4 n$ (Cell C7). Ratio $E [X] / (n ln n)$ as $n \to \infty$ … ::: tends to $2$ (Cell C7). Given the whole array's first pivot is a middle element $z_{k}$ with $i < k < j$ , $Pr [z_{i} \leftrightarrow z_{j}]$ … ::: $0$ — they are split apart forever (Cell C9).