294 views
0 votes
0 votes
Once the tournament finishes, pick up the logN competitors that were beaten by the tournament winner and hold a mini-tournament to find which one is the best among them. If we imagine that better players correspond with smaller numbers, the algorithm now goes like this. Hold the tournament to find the smallest number (requires N−1 comparisons). During this step, for each number construct the list of numbers it was smaller than. Finally, pick the list of numbers associated with the smallest number and find their minimum in logN−1l steps. This algorithm requires N+logN−2 comparisons to complete

 

How is the competitors beaten by tournament winner log N ?

Please log in or register to answer this question.

Related questions

0 votes
0 votes
1 answer
1
Sahil Gupta asked Nov 25, 2014
813 views
In a round-robin tournament with m players, every two players play one game in which one player wins and the other loses. We want to find conditions on positive integers ...