Just to revisit the upper bound in the case of the top three. It is not too difficult to construct the right algorithm.Let L(n) = k, meaning . We start with a standard KO tournament to determine the winner. players get a first-round bye and the rest play it out for the second round. The number of players who make it to the second round is,and the rest is a regular KO to pick the winner. Obviously, the number of games played so far is (n-1) since everyone but the winner lost exactly one game.We then determine the runner-up in a straightforward fashion: there are at most k contenders - those who lost to the winner. We assign each of them the number (1 through k) of the round in which he lost. (In case the winner got a bye, no one gets #1.) We have #1 play #2, then the winner of this game play #3, and so on. The winner of the last game is the runner-up, and we just had at most (k-1) more games. It is easy to see that the runner-up could have won k games at most, and so it requires at most (k-1) more games to determine the third best. Therefore, the number of games we had was no greater than(n-1) + (k-1) + (k-1) = 2L(n) + n-3,exactly as claimed earlier.

This works the same way for k>=4. The order chosen for the candidate for rank 4, is so that those who won less games play first e.g.

I think I understand now where I failed.In the example I gave below:{6, 15, 5, 9, 7, 2, 4, 10, 1, 16, 12, 11, 13, 8, 14, 3}{{{6, 15}, {5, 9}, {2, 7}, {4, 10}, {1, 16}, {11, 12}, {8, 13}, {3, 14}},{{5, 6}, {2, 4}, {1, 11}, {3, 8}},{{2, 5}, {1, 3}},{{1, 2}}}{{{11, 16}, {2, 3}},{{2, 11}}}{{{4, 7}, {3, 5}, {11, _}, {_, _}},{{3, 4}, {11, _}},{{3, 11}}}Instead of doing a 2nd KO, we take the set{16, 11, 3, 2}and play{{11,16},{3,11},{2,3}}and we look for the 3rd best in the union of{7,4,5} and {3}, we eliminate 11.Using that logic and rewriting my earlier conclusion:C must be in either of the following subsets:(i) 0 to L[n]-1 players defeated by B on the first KO (ii) 1 to L[n]-1 players defeated by B on the "bubble" 2nd tournamentSo C must win a 3rd tournament with L[n]-1 (minimum) to L[n] (maximum) players.But there's an interesting example:{16, 7, 13, 8, 1, 3, 14, 2, 9, 5, 4, 10, 12, 11, 15, 6}{{{7, 16}, {8, 13}, {1, 3}, {2, 14}, {5, 9}, {4, 10}, {11, 12}, {6, 15}}, {{7, 8}, {1, 2}, {4, 5}, {6, 11}}, {{1, 7}, {4, 6}}, {{1, 4}}}So if we do the bubble 2nd tournament:{{2, 3}, {2, 7}, {2, 4}}We have to find the 3rd in the union of the sets:{14} (loser to B in 1st tournament) and{3, 7, 4} (losers to B in 1st tournament)and we'll have 3 another comparisons so arrive at sevvost's upper bound 2 L[n] + n - 3.But a KO 2nd tournament will be:{{{2, 3}, {4, 7}}, {{2, 4}}}and the 3rd is to be found in the set{14, 3, 4} which takes 2 comparisons ...So my question is then:If we apply the bubble do we reduce the upper bound at the expense of increasing the lower bound, and conversely if we apply KOs do we reduce the lower bound at the expense of increasing the upper bound ?

Hmm, sorry this is approximate and not exact, but I know for the complete ranking you don't need more than O(N log N) since that's the lower (and upper) bound on comparison sortinghttp://en.wikipedia.org/wiki/Comparison_sort

Agreed, but we were looking for the fastest way of finding the first n players without having to do the full sort.So far it seems everyone agrees on the number of comparisons for the first 2 players.I still have doubts about the 3rd player; for me if you choose a "bubble" comparison to find the 2nd and the 3rd best players you have tighter bounds; if you continue using KO comparisons you have looser bounds, but the lower bound is lower than the bubble's.I have not calculated the expected number of comparisons using both methods yet, I'll have to return to this problem in one week or so.

An analysis of this problem does appear in Knuth's TAOCP vol 3, 5.3.3 Minimum-Comparison selection.For n=2, we have the formula already described below:V2(n)=W2(n)=n-2+Ceiling[Log[n]]where Vk(n) is the minimum number of comparisons needed to determine the kth better player, and Wk(n) is the minimum number of comparisons needed to determine the k better players collectively.Lower and upper bounds for V3 are:n + Ceiling[Log[(n-1)/3]] + Ceiling[Log[(n-1)/4]]andn + 1 + Ceiling[Log[(n-1)/4]] + Ceiling[Log[(n-1)/5]]and:W3(n) <= V3(n) + 1V3(n) <= V3(n-1) + 2Need more time to work out the examples.

Not sure if the following has anything to do with answering the problem. Just some thoughts right off the top of my head.For a_1<a_2<...<a_n, the # of different patterns that decide the first 'k' players are n!/(n-k)!For each compare of A and B, it gives only two possible outcomes: A>B or A<B. Therefore N comparisons can lead to 2^N patterns.In order to decide the first 'k' players through comparison, we need to make sure 2^N >= n!/(n-k)!, which meansN >= ceiling ( log_2 (n!) - log_2((n-k)!) )I believe this gives a lower bound for min # of comparisons.