There are n horses who have a transitive relation in terms of their speed (If A runs faster than B and B runs faster than C => A runs faster than C). We don’t have space to conduct a race of all the n horses. We can at most run 4 horses in a race. At least How many races do we need to have to find the two fastest horses?
The question can be asked in binary mode as well, i.e we can only run two horses at a time. How many comparisons do we need to make?
Or, Replace horses with numbers, There are n numbers from which you want to find the largest and the second largest, at least how many comparisons you need to make?
No comments:
Post a Comment