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

A divide-and-conquer algorithm divides an input into smaller instances, solves those instances recursively, and combines their answers. Directly solvable base cases terminate the recursion. The total time complexity includes both the recursive work and the work of dividing and combining; balanced sizes alone do not determine the running time.

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.

Put $\alpha ={\log }_{b}a$. With a nonnegative toll bounded by $O(n^d)$, the Master theorem gives the upper boundsIf the base cost is $\Theta (1)$ and the toll is $\Theta (n^d)$, these become the usual tight $\Theta$ bounds. The printed $O$ toll by itself does not imply those lower bounds; for example, the toll could vanish.

For the two requested proofs, let $n=b^k$ as permitted. Expanding the recurrence relation through $k$ levels givesWhen $d=\alpha$, the ratio is one. The sum has $k={\log }_{b}n$ terms, so $T(n)=O(n^d\log n)$. With matching positive lower bounds on each level's work, the same expansion gives $\Theta (n^d\log n)$.

When $d>\alpha$, the ratio $r=a/b^d$ is strictly below one. The geometric series is at most $1/(1-r)$, so the internal work is $O(n^d)$; the leaf term $O(n^{\alpha })$ is also $O(n^d)$. A $\Theta (n^d)$ root toll supplies the matching lower bound in the tight version. This proves both requested cases.

There is a small termination qualification in the printed generality: if $1<b<2$, the literal base case only at $n=1$ may leave ceil(n/b) = n at a small integer, for example $n=2,b=3/2$. The standard rounded Master theorem assumes a sufficiently large fixed base-case cutoff so that recursive sizes decrease. The allowed unrounded powers-of-$b$ proof above does not use that problematic rounded step. Also, a literal number of recursive calls is integral, though the algebraic recurrence expansion remains meaningful for positive real $a$.

Maintain an inclusive interval $[lo,hi]$ with these recursion invariants: if $lo>0$, then $A[lo]>A[lo-1]$; if $hi<n-1$, then $A[hi]>A[hi+1]$. The original full interval satisfies both conditions vacuously.In the left-recursion branch, the new right endpoint satisfies $A[m-1]>A[m]$ and the old left boundary is retained. The right-recursion branch is symmetric. Thus both recursion invariants persist.

If neither branch is taken, $A[m]$ exceeds its neighbours within the current interval because all entries are distinct. If $m$ is an endpoint of that interval and there is a neighbour outside, the boundary recursion invariant supplies the missing strict inequality. Hence the returned index is an array local maximum with respect to the original array, not just the restricted interval. Every branch shortens the interval, so termination is guaranteed; this also establishes existence, including the singleton case.

Each call performs at most two comparisons, and a recursive interval has at most half as many elements, up to rounding. Thus $T(n)\le T(\lceil n/2\rceil )+O(1)$ andThe conventional bound is $O(\log n)$ for $n\ge 2$, with constant work for a singleton. Distinctness is essential to this proof of a strict local maximum.