Question

How many comparisons does the tournament sort use tofind the second largest, the third largest, and so on, up tothe \({\left( {{\bf{n - 1}}} \right)^{{\bf{st}}}}\) largest (or second smallest) element?

Short answer

n−1, where \(n = {2^k}\)

Step-by-step solution

We need to find a number of comparisons needed to find the second largest up to the second smallest element.

One shall find a number of comparisons needed to find the second largest up to the second smallest element.

Now find the total number of comparisons.

Total number of comparisons required for finding any largest element would be

\(\begin{array}{l}1 + 2 + 4 + ... + {2^k}\\ \Rightarrow {2^0} + {2^1} + {2^2} + ... + {2^k}\end{array}\)

where\({2^{k + 1}} = n \Rightarrow k = lo{g_2}\left( {\frac{n}{2}} \right)\)

\( \Rightarrow {2^0}\left( {\frac{{{2^{log\frac{n}{2} + 1}} - 1}}{{2 - 1}}} \right)\)(By Sum of geometric series formula)

\(\begin{array}{l} \Rightarrow \frac{n}{2} \times 2 - 1\\ \Rightarrow n - 1\end{array}\)