Sorting & Searching

Question 1

(a) Decision-tree lower bound (9 marks)

Model (1 mark). A comparison sort accesses input only via comparisons $a_i \lessgtr a_j$. Its execution on all inputs of size $n$ forms a binary decision tree: each internal node is a comparison with two outcomes (branches), each leaf a permutation output.

Leaves ≥ n! (2 marks). For the algorithm to be correct, every one of the $n!$ distinct orderings of distinct inputs must lead to a distinct leaf (each requires a distinct output permutation). Hence the number of leaves $L \ge n!$. Why: two inputs requiring different sorted rearrangements cannot follow identical comparison outcomes yet produce the correct answer.

Height bound (2 marks). A binary tree of height $h$ has at most $2^h$ leaves. Therefore $2^h \ge L \ge n! \;\Rightarrow\; h \ge \log_2(n!).$ The worst-case comparison count equals the longest root-to-leaf path $=h$.

Stirling estimate (4 marks). Using (1), $\log_2(n!) = \frac{\ln(n!)}{\ln 2} = \frac{n\ln n - n + O(\ln n)}{\ln 2} = n\log_2 n - n\log_2 e + O(\log n).$ The leading term is $n\log_2 n$, so $h \ge n\log_2 n - 1.4427\,n + O(\log n) = \Omega(n\log n)$. ∎

(b) Average-case (5 marks)

The average number of comparisons equals the average leaf depth $\bar d$ of the tree (2 marks). A binary tree with $L$ leaves has average leaf depth $\bar d \ge \log_2 L$ (a "balanced" tree minimizes average depth; formally by Kraft/entropy, $\bar d \ge \log_2 L$) (1 mark). With $L \ge n!$: \bar d \ge \log_2(n!) = n\log_2 n - \Theta(n) = \Omega(n\log n). \tag{2 marks} So even the average case is $\Omega(n\log n)$. ∎

(c) Landauer energy (6 marks)

Minimum comparisons in worst case $\ge \lceil\log_2(n!)\rceil$ (1 mark). Compute for $n=10^6$: $\log_2(n!) \approx n\log_2 n - n\log_2 e.$ $\log_2(10^6) = 6\log_2 10 = 6(3.32193) = 19.9316$. $n\log_2 n = 10^6 \times 19.9316 = 1.99316\times10^7$. $n\log_2 e = 10^6 \times 1.44270 = 1.44270\times10^6$. So $\log_2(n!) \approx 1.99316\times10^7 - 0.144270\times10^7 = 1.8489\times10^7$ comparisons (2 marks).

Energy per erased bit: $k_B T\ln 2 = 1.38\times10^{-23}\times300\times0.6931 = 2.870\times10^{-21}\,\text{J}$ (1 mark).

Total minimum: $E \ge 1.8489\times10^7 \times 2.870\times10^{-21} = 5.31\times10^{-14}\,\text{J} \approx \mathbf{5.3\times10^{-14}\,J}$ (1 mark).

Comment (1 mark): Counting sort does not use element-vs-element comparisons; it uses key values as array indices (bucketing). The $\Omega(n\log n)$ bound applies only to the comparison model, so counting sort's $O(n+k)$ sidesteps both the decision-tree bound and this Landauer floor (though it dissipates energy per array write instead).

---

Question 2

(a) Comparison probability (7 marks)

Let $z_1 < z_2 < \dots < z_n$ be sorted order. Consider the set $Z_{ij}=\{z_i,\dots,z_j\}$.

Claim: $z_i$ and $z_j$ are compared iff the first element of $Z_{ij}$ chosen as a pivot is $z_i$ or $z_j$ (3 marks).

• Comparisons only occur against a pivot. While no element of $Z_{ij}$ is chosen as pivot, all of $Z_{ij}$ stays in the same partition (any pivot outside $Z_{ij}$ is either $<z_i$ or $>z_j$, so does not separate them).
• Once some $z_m\in Z_{ij}$ is picked first: if $i<m<j$, then $z_i,z_j$ go to opposite partitions and are never compared. If $m=i$ or $m=j$, the pivot is compared with everything in the set, so $z_i,z_j$ are compared. Each pair is compared at most once (a pivot is removed after partition).

Probability (4 marks). Among the $|Z_{ij}| = j-i+1$ elements, each is equally likely to be the first chosen as pivot (uniform random pivots). Favourable outcomes: $z_i$ or $z_j$ first, i.e. $2$ of $j-i+1$: $\Pr[X_{ij}=1] = \frac{2}{j-i+1}. \qquad ∎$

(b) Expectation (7 marks)

By linearity: $E[X]=\sum_{i<j}\Pr[X_{ij}=1]=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\frac{2}{j-i+1}$ (1 mark).

Substitute $k=j-i$ ($k$ runs $1\dots 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+1} < \sum_{i=1}^{n-1} 2\sum_{k=1}^{n}\frac1k = 2(n-1)H_n. \tag{4 marks} Since $H_n = \ln n + \gamma + O(1/n)$, E[X] < 2nH_n = 2n\ln n + O(n) = O(n\log n). \qquad ∎ \tag{2 marks}

(c) Adversarial median-of-three (6 marks)

Pseudocode (3 marks):

QUICKSORT(A, lo, hi):
  if lo < hi:
    p = HOARE_PARTITION(A, lo, hi)
    QUICKSORT(A, lo, p)
    QUICKSORT(A, p+1, hi)

HOARE_PARTITION(A, lo, hi):
  mid = (lo+hi)//2
  # median-of-three: median of A[lo], A[mid], A[hi]
  pivot = median(A[lo], A[mid], A[hi])
  i = lo-1; j = hi+1
  while true:
    do i=i+1 while A[i] < pivot
    do j=j-1 while A[j] > pivot
    if i >= j: return j
    swap A[i], A[j]

Adversarial input (3 marks). Median-of-three only guarantees the pivot is not the extreme of the three sampled positions; it can still be near-extreme of the whole array. A "median-of-three killer" arranges that each recursive call's sampled median is the second-smallest remaining element. One concrete $n=7$ instance: $A = [1,\,7,\,3,\,2,\,5,\,4,\,6].$ Here positions $lo=0,mid=3,hi=6$ hold $1,2,6$; median $=2$, the 2nd smallest. Partition splits off just one element, leaving a size-6 subproblem whose sampled median is again near-minimal. Recursively the split is $\{1\text{ element}\}$ vs $\{n-1\}$, giving depth $\Theta(n)$ and total work $\sum k = \Theta(n^2)$. Why it defeats the heuristic: median-of-three protects only against the fully sorted/reverse-sorted patterns; an adversary who knows the fixed sampling positions can plant a permutation making the sampled median an extreme rank of the actual data.

---

Question 3

(a) Structural lemma (7 marks)

Algorithm (2 marks): Partition $A$ into $\lceil n/5\rceil$ groups of ≤5; sort each and take its median (the "medians"). Recursively SELECT the median-of-medians $x$ of these $\lceil n/5\rceil$ medians. Partition $A$ around $x$; recurse into the side containing rank $k$.

Guarantee (5 marks): At least half of the $\lceil n/5\rceil$ groups contribute a median $\le x$... consider medians $\ge x$: there are $\ge \lceil \tfrac12\lceil n/5\rceil\rceil$ such group-medians. In each such group, the median plus the 2 elements above it (3 elements) are $\ge x$, except possibly the group containing $x$ itself and the last (partial) group — subtract 2 groups. Thus the number of elements $\ge x$ is $\ge 3\left(\left\lceil\tfrac12\left\lceil\tfrac n5\right\rceil\right\rceil - 2\right) \ge 3\left(\frac{n}{10}-2\right) = \frac{3n}{10}-6.$ By symmetry $\ge 3n/10-6$ elements are $\le x$. Hence each recursive partition discards $\ge 3n/10-6$ elements, so the surviving side has $\le n-(3n/10-6)=7n/10+6$ elements. ∎

(b) Recurrence and substitution (9 marks)

Costs (2 marks): median-finding recursion on $\lceil n/5\rceil$ medians $=T(n/5)$; recursive select on the ≤$7n/10+6$ side $=T(7n/10+6)$; grouping, group-medians, partition $=O(n)=an$: $T(n) \le T(n/5) + T(7n/10+6) + an.$

Substitution (5 marks): Guess $T(n)\le cn$ for $n> n_0$. Then $T(n) \le c\frac n5 + c\left(\frac{7n}{10}+6\right)+an = cn\left(\frac15+\frac{7}{10}\right)+6c+an = \frac{9}{10}cn + 6c + an.$ Require $\frac{9}{10}cn+6c+an \le cn$, i.e. $an+6c \le \frac{1}{10}cn$, i.e. $c \ge \frac{10an}{n-60}\quad\Longrightarrow\quad \text{for } n\ge 120,\ \frac{n}{n-60}\le 2,\ \text{take } c = 20a.$ So $T(n)=O(n)$. (Set base case $c$ large enough for $n\le120$.) (2 marks)

Why groups of 3 fail (2 marks): With groups of 3 the pivot exceeds only $\ge 2(\lceil\tfrac12\lceil n/3\rceil\rceil-2)\approx n/3-O(1)$ elements, so the recursion is $T(n)\le T(n/3)+T(2n/3)+O(n)$. Coefficients $\tfrac13+\tfrac23=1$, so the guessed substitution gives $T(n)\le cn+O(n)$ — the linear guess fails; solving exactly yields $T(n)=\Theta(n\log n)$, not linear.

(c) General group size (4 marks)

With odd group size $g$: median-finding costs $T(n/g)$. The pivot exceeds $\ge \frac{\lceil g/2\rceil}{g}\cdot\frac n2$ elements (half the groups, $\lceil g/2\rceil$ each, over $n/g$ groups → to leading order $\tfrac{\lceil g/2\rceil}{g}\cdot\tfrac n2$). Surviving side $\le n - \tfr