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

The standard three-case master theorem concernswith constant base-case cost and eventually nonnegative $f$. Put $d={\log }_{b}a$.

In a divide-and-conquer algorithm, $a$ counts recursive subproblems, $n/b$ is their size, and $f$ accounts for splitting and combining. The comparison with $n^{{\log }_{b}a}$ identifies whether leaves, all levels, or the upper levels dominate the running time. The polynomial gap and the third case's regularity condition are part of this version of the theorem.

Build a balanced comparison tournament, retaining the record of each value's direct defeats. A record stores a key and a list of records that it directly defeated:There is one key comparison at each merge. Because $S$ is a set, all keys are distinct, so the greater winner is unambiguous. Retaining the losing record also retains its own earlier comparison history; it does not merely retain the losing root's value.

Let the returned root have value $M$. DefineThe second-largest value can only lose to $M$, so it occurs among those direct losers. This proves the required partition and the exclusion of the second-largest value from the third part. For $n=2^m$, the winner participates in exactly $m$ merges, so $|\mathrm{second}(S)|=m$. The other part can be materialized by marking the original element identities in this list and scanning the original inputs, using $O(n)$ additional operations without more comparisons between keys.

The first value is the tournament winner $M$. Find the second value $s$ by taking the maximum of the direct-loser set $\mathrm{second}(S)$, retaining its associated tournament record.

The third-largest value must have lost directly to either $M$ or $s$: any other value is smaller and could not defeat it. Therefore it belongs toConversely, every value in $C$ is distinct from $M,s$. Thus the third-largest value is $\max C$. This is tournament selection of the three largest elements; it uses the retained defeat records while computing the requested three-part partition.

Three largest elements exist only for $n\ge 3$. With the paper's power-of-two assumption this means $n\ge 4$. The partition in part (b) remains meaningful for $n=2$, but a third output cannot be supplied in that case.

The balanced comparison tournament usesso $C(n)=n-1$. The second-largest search compares $m={\log }_{2}n$ direct losers, using $m-1$ comparisons. The record of $s$ contains at most $m-1$ direct losers, because $s$ loses before becoming the overall winner. Hence the third candidate set has size at most $2m-2$, requiring at most $2m-3$ comparisons.

For $n=2^m\ge 4$, the complete comparison count is thereforeThis is $n+O(\log n)$ and therefore meets the requested $O(n+{\log }^{2}n)$ bound. The defeat-record lists can be linked in constant local work per merge; flattening the final partition takes $O(n)$ work. Thus the method also has linear overall running time under constant-cost key comparisons.