Quick sort randomization — expected O(n log n)

WHAT is randomized quicksort?

QUICKSORT(A, lo, hi):
    if lo < hi:
        r = RANDOM(lo, hi)          # <-- the only new line
        swap A[r] with A[hi]        # move random pivot to the end
        p = PARTITION(A, lo, hi)    # Lomuto/Hoare around A[hi]
        QUICKSORT(A, lo, p-1)
        QUICKSORT(A, p+1, hi)

HOW the cost is counted — comparisons are everything

All the real work of quicksort is in comparisons done during partitioning. So if we bound the expected number of comparisons, we bound the runtime.

The key probability (derive it!)

Formula Probability that

$z_i$ and $z_j$ are compared Consider the set $Z_{ij} = \{z_i, z_{i+1}, \dots, z_j\}$ — the $j-i+1$ elements between them in sorted order. Trace the recursion: the first of these elements ever chosen as a pivot decides everything.

If that first pivot is $z_i$ or $z_j$ → they get compared (one is the pivot, the other is in its subarray). ✅
If the first pivot is some middle $z_k$ ( $i<k<j$ ) → $z_i$ and $z_j$ land in different partitions and are never compared. ❌

Because every element of $Z_{ij}$ is equally likely to be the first one chosen as a pivot (random pivots!), and there are $j-i+1$ of them, exactly $2$ of which are "good": $\Pr[z_i \leftrightarrow z_j] = \frac{2}{j-i+1}$

Why this step? Every element in $Z_{ij}$ has the same chance of being picked first as a pivot — that's the whole payoff of uniform randomization. Two favorable choices out of $j-i+1$ → probability $2/(j-i+1)$ .

Summing up → the bound

$E[X] = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\frac{2}{j-i+1}$

Substitute $k = j-i$ (so $j-i+1 = k+1$ ). For each $i$ , $k$ ranges $1\to n-i$ :

$E[X] = \sum_{i=1}^{n-1}\sum_{k=1}^{n-i}\frac{2}{k+1} < \sum_{i=1}^{n-1}\sum_{k=1}^{n}\frac{2}{k} = \sum_{i=1}^{n-1} 2 H_n$

where $H_n = \sum_{k=1}^n \frac1k$ is the harmonic number, and $H_n = \Theta(\ln n)$ .

$\boxed{E[X] < 2(n-1)H_n = O(n\log n)}$

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

Worked examples

Common mistakes

Active recall

Recall Test yourself (open after attempting)

When are two elements ever compared in quicksort? → only when one is the pivot.
Why is $\Pr[z_i\leftrightarrow z_j]=\frac{2}{j-i+1}$ ? → first pivot in $Z_{ij}$ decides; 2 good out of $j-i+1$ .
Why does randomization beat the adversary? → cost depends on coin flips, not input order.
Worst case of randomized quicksort? → still $O(n^2)$ (just improbable).

What does randomization change about quicksort's complexity?

Worst case stays

O(n^2)

but expected time becomes

O(n\log n)

for every input; no input is adversarially bad.

When are two elements

z_i,z_j

compared in quicksort?

Exactly when one of them is chosen as a pivot while both are still in the same subarray — at most once.

What is

\Pr[z_i \text{ and } z_j \text{ are compared}]

\dfrac{2}{j-i+1}

, since the first of the

j-i+1

elements between them (inclusive) to be picked as pivot must be

z_i

z_j

Why is the indicator

X_{ij}

either 0 or 1?

A pair is compared at most once because the pivot involved is removed from future recursion; opposite-side elements are never compared again.

What is

E[X]

in closed form?

E[X]=\sum_{i<j}\frac{2}{j-i+1} < 2(n-1)H_n = O(n\log n)

, where

H_n=\Theta(\ln n)

What is the harmonic number

H_n

asymptotically?

H_n=\sum_{k=1}^n 1/k \approx \ln n + 0.577

, so

\Theta(\log n)

Probability two adjacent (in sorted order) elements are compared?

\frac{2}{2}=1

— adjacent elements are always compared.

Does a single random shuffle at the start work as well as random pivots?

Yes — both make pivot ranks uniformly random, giving the same expected

O(n\log n)

Recall Feynman: explain it to a 12-year-old

Imagine sorting a deck of cards by picking one card (the "splitter"), then putting smaller cards left and bigger cards right, and repeating on each pile. If you always pick the smallest card as splitter, your piles are lopsided (1 vs the rest) and it takes forever. The trick: pick the splitter card at random each time. Now there's no sneaky way for someone to arrange the deck to slow you down — because they can't guess which card you'll grab. On average your piles split nicely in half, so you finish in about $n\log n$ steps instead of $n^2$ . Two cards only ever get directly compared if one of them happens to be a splitter while they're still in the same pile — and that gives the neat little fraction $2/(\text{gap}+1)$ .

Connections

Quicksort (deterministic) — same partition logic, worst-case $O(n^2)$ on sorted input.
Linearity of Expectation — the engine that lets us sum per-pair probabilities.
Indicator Random Variables — $X_{ij}$ technique reused across randomized algorithms.
Harmonic Number $H_n=\Theta(\ln n)$ — source of the $\log$ factor.
Merge Sort — deterministic guaranteed $O(n\log n)$ , contrast on stability/space.
Median of Medians — deterministic good-pivot selection, alternative to randomizing.
Las Vegas vs Monte Carlo algorithms — quicksort is Las Vegas (always correct, time random).

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, normal quicksort ka problem yeh hai ki agar pivot hamesha pehla ya aakhri element lo, toh koi smart banda tumhe already sorted array de dega — aur tumhara pivot har baar sabse chhota/bada niklega. Tab ek side mein $n-1$ elements aur doosri side khaali — recursion depth $n$ ho gaya, time $O(n^2)$ . Yani input ka order tumhe maar deta hai.

Solution simple hai: har step pe pivot ko randomly uthao (uniformly). Ab badi baat — cost ab input ke order pe depend nahi karta, balki tumhare coin flips pe karta hai. Adversary kitna bhi clever ho, woh tumhare random choices guess nahi kar sakta, toh koi bhi input "bad input" nahi reh jaata. Isliye expected time har input ke liye $O(n\log n)$ ho jaata hai.

Proof ka core idea: do elements $z_i$ aur $z_j$ (sorted order mein) sirf tab compare hote hain jab unme se ek pivot bane. Unke beech ke $j-i+1$ elements mein se jo pehla pivot banta hai, wahi decide karta hai — agar woh $z_i$ ya $z_j$ hua toh compare honge, beech wala koi hua toh alag piles mein chale jaayenge. Toh probability $= 2/(j-i+1)$ . Sab pairs ka expectation jodo (linearity of expectation), gap substitute karo, aur harmonic series $H_n \approx \ln n$ aa jaata hai — final answer $O(n\log n)$ .

Yaad rakhna ki worst case abhi bhi $O(n^2)$ hai — bas uski probability itni kam hai ki practically kabhi nahi aata. Random pivot "bad luck" nahi hataata, "bad input" hataata hai. Yeh technique (indicator variables + linearity) interviews aur exams mein bahut kaam aati hai, toh derivation rata mat, samajh ke yaad rakho.

Quick sort randomization — expected O(n log n)

WHAT is randomized quicksort?

HOW the cost is counted — comparisons are everything

The key probability (derive it!)

Summing up → the bound

Worked examples

Common mistakes

Active recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Sorting & Searching

Connections