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 / d

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.