Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 5 / b / Solution

For one element, return it as both extrema without a comparison. Otherwise compare consecutive pairs once, put each smaller element in a candidate array $L$ and each larger element in a candidate array $H$. If one element is unpaired, put it in both candidate arrays. This simultaneous minimum and maximum construction computes the minimum of $L$ and maximum of $H$ by balanced divide-and-conquer algorithms: split the candidate array, recursively find the desired extremum in each half, and compare the two returned values. These extremum routines use one comparison per merge and therefore $r-1$ comparisons on $r$ candidates.

Every element excluded from $L$ is at least its paired element, so a global minimum remains in $L$; likewise a global maximum remains in $H$. The recursive extremum routines are correct by structural induction. For even $n=2m$, there are $m$ pair comparisons and two searches on $m$ candidates, givingFor odd $n=2m+1\ge 3$, there are $m$ pair comparisons and two searches on $m+1$ candidates, givingTogether with $C(1)=0$, both cases giveFor powers of two, the equivalent direct divide-and-conquer algorithm returns the ordered pair of extrema for each half, then combines the two minima with one comparison and the two maxima with one comparison. Its base cases must include $C(2)=1$, rather than performing two unnecessary comparisons on a pair. The recurrence relation is $C(n)=2C(n/2)+2$ for $n\ge 4$, whence $C(n)=3n/2-2$. Arbitrary near-equal splitting without the initial pairing can exceed the desired comparison bound for other values of $n$; the pairing construction above handles every positive size.