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

• Two elements are compared only when one is the pivot. After a pivot splits the array, elements on opposite sides never meet again. So each pair is compared at most once.
• The compare probability. If $z_1<z_2<\cdots <z_n$ are the elements in sorted order (so $z_i$ is the $i$-th smallest), then $z_i$ and $z_j$ are compared with probability $\frac{2}{j-i+1}$. Here $j-i$ is just the gap — how far apart they sit in sorted order.
• The total. Expected comparisons $E[X]=\sum _{i<j}\frac{2}{j-i+1}$, and this is $<2(n-1)H_n=O(n\log n)$, where $H_n=1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}$ is the harmonic number.

(a) Worst case is still $O(n^2)$ — you could flip unlucky coins that always pick an extreme pivot. (b) Expected time is $O(n\log n)$ for every input. Randomization removes bad inputs, not bad luck.

$\mathrm{Pr}[z_i\leftrightarrow z_j]=\frac{2}{j-i+1}=\frac{2}{d+1}$. The set $Z_{ij}=\{z_i,\dots ,z_j\}$ has $j-i+1=d+1$ members; exactly $2$ of them ($z_i$ and $z_j$) are "good" first-pivots.

With ranks $1,\dots ,6$, a pair with gap $d$ needs $i$ and $i+d$ both in range, so $i$ runs $1\dots 6-d$, giving $6-d$ pairs.

Total pairs $=5+4+3+2+1=15=\left(\genfrac{}{}{0ex}{}{6}{2}\right)$. ✅

Group by gap $d$, using count $=4-d$ and probability $\frac{2}{d+1}$:

• $d=1$: $3$ pairs $\times \frac{2}{2}=1\Rightarrow 3$
• $d=2$: $2$ pairs $\times \frac{2}{3}\Rightarrow \frac{4}{3}$
• $d=3$: $1$ pair $\times \frac{2}{4}\Rightarrow \frac{1}{2}$

$E[X]=3+\frac{4}{3}+\frac{1}{2}=\frac{18+8+3}{6}=\frac{29}{6}\approx \mathrm{4.833.}$

Count $=5-d$, probability $\frac{2}{d+1}$:

• $d=1$: $4\times 1=4$
• $d=2$: $3\times \frac{2}{3}=2$
• $d=3$: $2\times \frac{2}{4}=1$
• $d=4$: $1\times \frac{2}{5}=\frac{2}{5}$

$E[X]=4+2+1+\frac{2}{5}=\mathrm{7.4.}$

$\mathrm{Pr}=\frac{2}{1+1}=1$ — they are always compared. Reason: the set between them is just $Z_{ij}=\{z_i,z_j\}$, only two elements. Whichever of the two is picked as a pivot first, the other is still in its subarray, so a comparison happens. There is no "middle" element that could separate them. Adjacent elements can never be split apart before one becomes a pivot.

Start from $E[X]={\sum }_{i<j}\frac{2}{j-i+1}$. Set $d=j-i$. For a fixed gap $d$, the pair $(i,i+d)$ is valid whenever $1\le i$ and $i+d\le n$, i.e. $i$ runs from $1$ to $n-d$. That is exactly $n-d$ pairs, each contributing the same probability $\frac{2}{d+1}$ because the probability depends only on $d$. Grouping them: $E[X]={\sum }_{d=1}^{n-1}\underset{\#\text{pairs}}{\underbrace{(n-d)}}\cdot \underset{\mathrm{Pr}}{\underbrace{\frac{2}{d+1}}}.$ Why regroup? The original sum has two indices but only one quantity that matters — the gap. Collapsing to $d$ turns a messy double sum into a single sum we can bound.

From L3.1, $E[X]={\sum }_{d=1}^{n-1}(n-d)\frac{2}{d+1}<{\sum }_{d=1}^{n-1}n\cdot \frac{2}{d+1}$ (dropping the $-d$ only makes each term larger). Let $k=d+1$, so as $d$ runs $1\dots n-1$, $k$ runs $2\dots n$: $=2n{\sum }_{k=2}^n\frac{1}{k}<2n{\sum }_{k=1}^n\frac{1}{k}=2n{H}_n.$ Since $H_n=\Theta (\ln n)$, this is $O(n\log n)$.

Reading the figure below. The bars visualise why $H_n={\sum }_{k=1}^n\frac{1}{k}$ grows only like $\ln n$. The horizontal axis is $k$ (the index of each harmonic term); the vertical axis is the value $1/k$. Each lavender bar sits over the interval $[k,k+1)$ with height $1/k$, so its area equals the harmonic term $1/k$ — and the total bar area is exactly $H_n$. The coral curve is $y=1/x$, whose area from $1$ to $n$ is ${\int }_1^n\frac{dx}{x}=\ln n$. Because every bar's top-left corner touches the curve while the bar overhangs to the right, the bars trap $H_n$ between $\ln n$ and $1+\ln n$. That is the picture behind "$H_n=\Theta (\ln n)$", which turns $E[X]$ into $O(n\log n)$.

$E[X]={\sum }_{d=1}^{n-1}(n-d)\frac{2}{d+1}=2n{\sum }_{d=1}^{n-1}\frac{1}{d+1}-2{\sum }_{d=1}^{n-1}\frac{d}{d+1}.$ The first piece is $2n(H_n-1)=\Theta (n\log n)$. The second piece: each $\frac{d}{d+1}<1$, so the whole second sum is $<n-1$, i.e. only $O(n)$. Therefore $E[X]=2n(H_n-1)-O(n)=\Theta (n\log n).$ The $\log$ factor is genuinely there — quicksort is not secretly linear.

Setup. At each step quickselect partitions the current live subarray around a random pivot, then keeps recursing only into the one side that still contains the target rank $k$. The work done at a step is one partition pass, which costs a comparison for each element of the live subarray — so the total comparison count is just the sum of the sizes of the live subarrays over all steps. Call the size at step $t$ the value $S_t$; the total is ${\sum }_t{S}_t$, and each partition costs at most $S_t$ comparisons. The constant we call $c$ below is simply the per-element bookkeeping cost of one comparison (a fixed number like $1$); it is a constant only so the final answer reads as $\Theta (n)$ rather than a specific count — you may set $c=1$ and read the argument as counting comparisons directly.

Why the subarray shrinks by a constant factor in expectation. A uniformly random pivot has a rank that is uniform in $\{1,\dots ,S_t\}$. Split $\{1,\dots ,S_t\}$ into quarters. With probability $\frac{1}{2}$ the pivot's rank lands in the middle half (between the $\frac{1}{4}$ and $\frac{3}{4}$ marks). Whenever it does, both resulting sides have size at most $\frac{3}{4}{S}_t$, so the side we keep is at most $\frac{3}{4}{S}_t$ no matter which side holds the target. Therefore, with probability at least $\frac{1}{2}$ the next live size is $\le \frac{3}{4}{S}_t$, and with the other $\frac{1}{2}$ it is at most $S_t$. The expected next size is thus at most $E[S_{t+1}\mid S_t]\le \frac{1}{2}\cdot \frac{3}{4}{S}_t+\frac{1}{2}\cdot S_t=\frac{7}{8}{S}_t.$ A "good split" (factor $\le \frac{3}{4}$) happens on at least half of steps, so the sizes shrink geometrically; using the looser per-step contraction $\frac{7}{8}<1$ already suffices, but the classic textbook bound uses the $\frac{3}{4}$ figure to say a good split arrives every $2$ steps in expectation.

The geometric sum. Because the expected live size after each good split is at most $\frac{3}{4}$ of the previous, the expected total work is bounded by a geometric series with ratio $\frac{3}{4}$: $E[\text{comparisons}]\le c\left(n+\frac{3}{4}n+{\left(\frac{3}{4}\right)}^{2}n+\dots \right)=c\cdot \frac{n}{1-\frac{3}{4}}=4cn=\Theta (n).$ Key contrast with sort: sorting must recurse into both sides (work $\Theta (n)$ at every level $\times$ $\log n$ levels), while selection follows one side (work forms a shrinking geometric sum, total $\Theta (n)$). The deterministic guaranteed-linear cousin is Median of Medians.

After a uniform shuffle, at every recursive call the elements inside a subarray are in uniformly random order, so the last element is a uniformly random pivot of that subarray — exactly the distribution random-pivot quicksort produces. Same pivot-rank distribution $\Rightarrow$ same compare probabilities $\frac{2}{d+1}$ $\Rightarrow$ same $E[X]=O(n\log n)$. Downside: the shuffle is an extra $O(n)$ pass and $O(n)$ random numbers up front, whereas random pivots draw randomness lazily, only as needed. Both are Las Vegas algorithms: always correct, runtime random.

(i) Worst case: merge sort is a guaranteed $\Theta (n\log n)$; randomized quicksort's worst case is $\Theta (n^2)$ but only with vanishing probability. (ii) Expected case: both $\Theta (n\log n)$; quicksort's constant factor is usually smaller (in-cache partitioning, no merge buffer). (iii) Memory: merge sort needs $\Theta (n)$ extra space for merging; quicksort sorts in place with $O(\log n)$ stack. (iv) An adversary cannot force merge sort's worst case (it has none) and cannot force randomized quicksort's worst case either (cost depends on hidden coin flips, not on the input) — but can force deterministic quicksort's $\Theta (n^2)$ with sorted input.

Substitute $k=d+1$ (so $d=k-1$, and $k$ runs $2\dots n$): $E[X]={\sum }_{k=2}^n(n-(k-1))\frac{2}{k}={\sum }_{k=2}^n\frac{2(n+1-k)}{k}=2(n+1){\sum }_{k=2}^n\frac{1}{k}-2{\sum }_{k=2}^{n}1.$ Now ${\sum }_{k=2}^n\frac{1}{k}=H_n-1$ and ${\sum }_{k=2}^{n}1=n-1$: $E[X]=2(n+1)(H_n-1)-2(n-1)=2(n+1)H_n-2(n+1)-2(n-1).$ Combine the last two: $-2(n+1)-2(n-1)=-4n$. Hence $\boxed{E[X]=2(n+1)H_n-4n.}$ Check against L2.2 ($n=5$): $H_5=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}=\frac{137}{60}$. Then $2\cdot 6\cdot \frac{137}{60}-20=\frac{1644}{60}-20=27.4-20=7.4$. ✅ Matches.

$n=4$: $H_4=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}=\frac{25}{12}$. Then $2\cdot 5\cdot \frac{25}{12}-16=\frac{250}{12}-16=\frac{250-192}{12}=\frac{58}{12}=\frac{29}{6}\approx 4.833$. ✅ Matches L2.1. $n=10$: $H_{10}=\frac{7381}{2520}\approx 2.928968$. Then $E[X]=2\cdot 11\cdot H_{10}-40=22\cdot 2.928968-40\approx 64.437-40=\mathrm{24.437.}$

Forecast: $H_{1000}\approx \ln 1000+0.5772=6.90776+0.5772=7.48496$. Estimate: $E[X]\approx 2(1001)(7.48496)-4000=2002\cdot 7.48496-4000\approx 14985.9-4000=\mathrm{10985.9.}$ Verify: the exact $H_{1000}=7.485471$, giving $2002\cdot 7.485471-4000=14985.92-4000=10985.92$. Relative error of the approximation: about $\frac{|10985.92-10985.9|}{10985.92}\approx 1.0\times 10^{-6}$ — the $\ln n+0.577$ approximation is essentially exact at this scale. This confirms $E[X]\approx 2n\ln n$ for large $n$.

Compare-probability $\frac{2}{d+1}$ (L1) → plug into small $n$ (L2) → collapse the double sum and bound it with $H_n$ (L3) → transfer the idea to selection, shuffling, and merge sort (L4) → nail the exact closed form $2(n+1)H_n-4n$ (L5).