= Solution
The balanced <comparison tournament> uses
$$
C(n)=2C(n/2)+1,\qquad C(1)=0,
$$
so $C(n)=n-1$. The second-largest search compares $m=\log_2n$ 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\geq4$, the complete comparison count is therefore
$$
\boxed{(n-1)+(m-1)+(2m-3)=n+3\log_2n-5.}
$$
This is $n+O(\log n)$ and therefore meets the requested $O(n+\log^2n)$ 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.
Back to article page
