No less than four grand slams are played every year to find the best tennis player in the world. These are knockout tournaments in which, at each stage half of the players lose and get out. Two [supposedly] best players clash in the finals and the winner of that game is declared the champion (the best player) and the loser the runner up (the second best player). All is fine with our champion but there is just a small problem with our runner up: He might not be the second best player of the tournament.
Let us assume that there were 16 players in the beginning with seedings 1 to 16, 16 being the best. Consider the following results for the matches in the tournament
15 15 1 15 5 9 9 16 12 16 16 16 4 4 3 16 11 11 6 11 7 10 10 14 2 8 8 14 13 14 14
As expected, 16 is the winner but the runner up is 14 not 15. 15 crashed out in the semi finals playing against the champion.
So what can we conclude from this?
- Runner up may not be the second best player of the tournament.
log nmatches are required to decide the best player in the tournament.
- We can find the second best player in the tournament looking at the match results of the winner which is a list of
log nplayers. At some point he must have defeated the second best player.
Here is a program that gives you the second best player in
(n - 1) + ((log n) - 1) = n + (log n) - 2 comparisons: