Quick sort randomization — expected O(n log n): Question bank

Before we start, five names we'll lean on (all built in the parent note):

Pivot — the element we partition around; everything smaller goes left, larger goes right.
Comparison — one "is $a < b$ ?" check; the parent proved all quicksort work is comparisons.
$z_{i}$ — the $i$ -th smallest element in sorted order (a rank label, not a position in the input).
$X_{ij}$ — an indicator: it equals $1$ if $z_{i}$ and $z_{j}$ are ever compared during the run, and $0$ otherwise. Because a pair is compared at most once, $X_{ij} \in {0, 1}$ .
$X$ — the total number of comparisons in a run, $X = \sum_{i < j} X_{ij}$ . Its expectation $E [X]$ is the quantity the whole analysis bounds ( $E [X] = O (n lo g n)$ ).
$Z_{ij}$ — the set ${z_{i}, z_{i + 1}, \dots, z_{j}}$ of the $j - i + 1$ elements lying between $z_{i}$ and $z_{j}$ (inclusive) in sorted order.

True or false — justify

Randomized quicksort's worst-case running time is

O (n lo g n)

False — the worst case is still $O (n^{2})$ (you could flip unlucky coins every level); only the expected time is

O (n lo g n)

Randomization makes quicksort's expected time

O (n lo g n)

only for random inputs.

False — the expectation is over the algorithm's coin flips, so it is

O (n lo g n)

for every fixed input, including sorted or adversarial ones.

Two elements

z_{i}

and

z_{j}

can be compared several times during a run.

False — a comparison only happens when one of them is the pivot, and pivots are removed from all future subarrays, so each pair is compared at most once.

Adjacent elements

z_{i}

and

z_{i + 1}

in sorted order are always compared.

True —

Pr = \frac{2}{( i + 1 ) - i + 1} = \frac{2}{2} = 1

; nothing sits between them, so whichever becomes a pivot first must compare against the other.

Shuffling the array once at the start is strictly weaker than picking random pivots.

False — a single uniform shuffle then deterministic pivoting gives the same expected

O (n lo g n)

; both make each pivot's rank uniformly random.

The probability

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

depends on where

z_{i}

and

z_{j}

sit in the input array.

False — it depends only on their sorted-order gap

j - i

; the input's physical arrangement is irrelevant after randomization.

Randomized quicksort is a Las Vegas algorithm.

True — it always returns the correct sorted output; only the running time is random. Compare with Las Vegas vs Monte Carlo algorithms.

If two elements land in different partitions after some pivot, they might still be compared later.

False — once a pivot splits them apart, they live in disjoint subarrays forever and are never compared again.

Spot the error

"Since we proved

E [X] = O (n lo g n)

, a run of length

n^{2}

is impossible."

The error: expectation is an average, not a maximum. An

O (n^{2})

run is possible but improbable — the bound only pins the average over coin flips.

X_{ij}

can be

2

because

z_{i}

could be a pivot once and

z_{j}

a pivot later."

The error: after

z_{i}

is a pivot it is removed, so it can never be compared to

z_{j}

again; each pair contributes at most one comparison, so

X_{ij} \in {0, 1}

"The first pivot chosen anywhere in the whole array decides whether

z_{i}, z_{j}

are compared."

The error: only the first pivot drawn from the set $Z_{ij} = {z_{i}, \dots, z_{j}}$ matters; a pivot outside that range keeps

z_{i}

and

z_{j}

together and settles nothing.

Pr [z_{i} \leftrightarrow z_{j}] = \frac{1}{j - i + 1}

because there are

j - i + 1

candidates."

The error: there are two favourable first-pivots (

z_{i}

z_{j}

), not one, so the numerator is

2

, giving

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

"Random pivots guarantee a balanced split at every level."

The error: they guarantee balance on average, not always — a random pivot can still be an extreme; the analysis sums probabilities, it doesn't promise each split is even.

"Because the harmonic number grows,

E [X]

Θ (n^{2})

The error:

H_{n} = Θ (lo g n)

, not linear; the bound is

2 (n - 1) H_{n} = Θ (n lo g n)

, with only one factor of

n

outside the log.

"Choosing the median as pivot every time is the same idea as randomization."

The error: exact median selection (Median of Medians) is a deterministic guarantee of balance; randomization achieves good balance in expectation far more cheaply, without computing a median.

Why questions

Why do we count comparisons instead of, say, swaps or array writes?

Because comparisons dominate quicksort's total work — bounding their expected number bounds the whole runtime up to constant factors.

Why can we split

E [X]

into a sum of per-pair probabilities?

By Linearity of Expectation:

E [\sum X_{ij}] = \sum E [X_{ij}]

, and for a 0/1 indicator,

E [X_{ij}] = Pr [X_{ij} = 1]

— no independence needed.

Why does every element of

Z_{ij}

have an equal chance of being the first pivot picked from it?

Pivots are drawn uniformly at random, so within any fixed subset the "first to be chosen" is uniform over that subset — that symmetry is the entire payoff of randomization.

Why does the adversary lose once we randomize the pivot?

The cost now depends on our coin flips, not on how the input is arranged; an adversary would have to predict the randomness, which they cannot.

Why is the harmonic number

H_{n} = \sum_{k = 1}^{n} \frac{1}{k}

the natural quantity here?

After substituting the gap

k = j - i

, the inner sum becomes

\sum \frac{2}{k + 1}

, which is bounded by

2 H_{n}

; see Harmonic Number for

H_{n} \approx ln n + 0.577

Why is randomized quicksort often preferred over Merge Sort despite the same

O (n lo g n)

Quicksort sorts in place with better cache behaviour and small constants; merge sort needs

O (n)

extra memory, though it guarantees

O (n lo g n)

worst case.

Why doesn't sorted input [1,2,3,4,5] cause the

O (n^{2})

blow-up anymore?

The pivot's rank is now uniformly random regardless of input order, so the split is balanced in expectation; the input being pre-sorted carries no information about the pivot.

Edge cases

What is the expected number of comparisons when

n = 1

Zero — a single-element (or empty) subarray triggers no partition, so no comparisons occur.

What happens if the subarray has all equal elements?

Behaviour depends on the partition scheme; naive Lomuto can degrade to

O (n^{2})

on all-equal keys, which is why three-way ("Dutch flag") partitioning is used — randomizing the pivot alone doesn't fix duplicates.

Is the pair

(z_{i}, z_{j})

ever compared when the very first pivot of the whole array is some

z_{k}

with

i < k < j

No — that pivot immediately separates

z_{i}

and

z_{j}

into different sides, so they are never compared: this is exactly the "middle pivot" losing case.

For the farthest pair

(z_{1}, z_{n})

, what is the probability they are compared, and is it the smallest such probability?

\frac{2}{n}

, the minimum over all pairs, since

j - i + 1 = n

is as large as possible — distant elements are the least likely to meet.

If we always pick the pivot to be the true median (never random), what is the running time?

A guaranteed

Θ (n lo g n)

worst case — but this needs deterministic median selection each level and larger constants; randomization trades the guarantee for cheaper expected performance.

Does the

O (n lo g n)

expectation still hold if the random pivot is chosen from only the first three elements?

Not for arbitrary input — "median-of-three from fixed positions" is deterministic and can be adversarially defeated; the guarantee needs the pivot's rank to be (near) uniform, which fixed-position sampling does not ensure.

Recall One-line summary to lock in

Randomization moves the risk from which input to which coin flips — worst case $O (n^{2})$ survives but becomes astronomically unlikely, and the expected cost is $O (n lo g n)$ on every input, driven entirely by the $\frac{2}{j - i + 1}$ pair-comparison probability.