Foundations — Quick sort randomization — expected O(n log n)

Before you can read the parent proof you need to be fluent with a handful of symbols and pictures. We build them one at a time, each earning its place before the next appears. Nothing below assumes you already know it.

0. A standing assumption — distinct elements

1. The array and "sorted order" — what $z_i$ means

An array is just a row of boxes holding numbers, in whatever messy order they arrived.

The figure below shows a messy input on top and the same values relabelled by rank $z_i$ underneath — trace the pink arrow to see how the physical value $1$ (sitting in slot 5) becomes the rank $z_1$.

Why the topic needs this. Quicksort never sorts by touching "position 3"; it sorts by value comparisons. Talking about $z_i$ (rank) instead of "the number in slot 3" lets us reason about which values get compared, independent of how jumbled the input was. That independence is exactly what randomization buys us.

2. What a comparison is, and the pivot

In the figure, the yellow box is the pivot ($6$). Follow the blue and pink arrows: everything smaller drops into the left chunk, everything larger into the right chunk. The caption underneath states the key consequence.

3. Probability — "what fraction of the time?"

Why this tool and not another. We can't predict the coin flips, so we can't say exactly how many comparisons happen on one run. Probability is the language for "on average, across all possible coin flips". That's the only honest thing to measure when the algorithm is random.

4. Expected value $E[\cdot ]$ — the average outcome

We introduce $E[\cdot ]$ before using it, because the "magic bridge" in the next section leans on it.

5. Random variables and the indicator $X_{ij}$

6. Linearity of expectation — adding the pieces

Why this tool. The total comparison count is $X={\sum }_{i<j}{X}_{ij}$, a sum of thousands of tangled indicators. Computing $E[X]$ directly is hopeless. Linearity lets us push $E$ inside the sum and handle each pair alone: $E[X]={\sum }_{i<j}E[X_{ij}]={\sum }_{i<j}\mathrm{Pr}[z_i\leftrightarrow z_j].$ This is the single most important move in the proof.

7. The gap $k=j-i$ and why probability depends only on it

Look again at the two elements $z_i$ and $z_j$. Between them (in sorted order) sits the set $Z_{ij}=\{z_i,z_{i+1},\dots ,z_j\},$ which has $j-i+1$ elements.

In the figure, the whole set $Z_{ij}$ is ringed; the two yellow ends are the "good" elements and the blue middles are the ones that split the pair apart. The double-headed pink arrow marks the gap that sets the count $j-i+1$.

Notice this depends only on the gap $k=j-i$, not on where the pair sits. That's why the parent substitutes $k=j-i$ to simplify the double sum.

8. The harmonic number $H_n$ and $\log$

The figure draws the curve $y=1/x$ in yellow with a blue rectangle of height $1/k$ and width $1$ for each term — the rectangles' total area is $H_n$, and it hugs the area under the curve, which is $\ln n$.

9. Collapsing the sum into $2(n-1)H_n$

Now watch the double sum turn into the harmonic number — this is the algebra the parent asserts.

Why the topic ends here. The final bound $E[X]<2(n-1)H_n$ is just the pair-probabilities summed and simplified. Recognising $H_n=\Theta (\log n)$ is what turns that sum into the headline result $O(n\log n)$.

Prerequisite map

Everything on the left builds the machinery; the two threads (indicators + linearity) and (the gap probability) merge into the single sum, which the harmonic number collapses into the final bound. Full proof: the parent topic. Compare with Quicksort (deterministic) and Merge Sort; the flavour of "random but always-correct" is Las Vegas vs Monte Carlo algorithms.

Equipment checklist

Cover the right side and test yourself — if any answer is fuzzy, re-read that section before the main proof.