Find the strongest person algorithm

Question

I'm wondering how one might solve the following problems better than what i have come up with. Basically you have n people and you want to find out who of those n people are the strongest, by letting them arm wrestle. I figured out how this can be solved with n-1 duels but are there any other solutions such as log(n) og 3n/2?

Thanks.

Answer 1

If we assume that strength is weakly-ordered, then it's the same as assuming that "If A is strong than B, and B is stronger than C, C is never stronger than A" for some A, B, C. That is, we can assume transitively that if "A is stronger than B", and "B is stronger than C", then also "A is stronger than C".

Our weakly-ordered contest, therefore will consist of each neighbor comparing themselves to their neighbor. This eliminates half the contestants in just one round (N/2 comparisons). We repeat this test of strength until only one person remains:

   O   O  O   O  O   O
    \ /    \ /    \ /
     O      O      O
      \    /       |
       \  /        |
         O         O
          \       /
           \     /
            \   /
              O

The time complexity of such an algorithm is O(N) and the number of "rounds" is floor(log_2(N)). In my example, N=6, and floor(log_2(6)) = 2. It's O(N) because we encounter a number of faceoffs in the form of N/2, then N/4, then N/8, ... then 1, leaving us with the summation N/2 + N/4 + N/8 + ... + 1, or the summation of N/(2ⁱ) for i from 0 to floor(log_2(N)), and since we know that floor(log_2(N)) is less than infinity we can safely say the result is less than or equal to the summation of the common geometric series multiplied by N, which is N. Hence O(N)

---

If we cannot assume weak ordering, then we end up in a scenario where A might beat B, and B might beat C, but C can beat A. There is no way to "sort" such a collection in order of strongest to weakest, so we are forced to have everyone square off against everyone so that we can compute a Wins/Losses record. Then we can order our competitors by their Wins. Such an algorithm to compute "all pairs" is O(N²) (Because the number of comparisons is the Triangular Numbers minus n):

• 1 faces off against 2, 3, 4 (3 faceoffs)
• 2 faces off against 3 and 4 (2 faceoffs, 2 already faced off against 1)
• 3 faces off against 4 (1 face off, already faced off against 1 and 2)

So we have a summation of faceoffs like (n-1) + (n-2) + ... + 1

Answer 2

Assuming that the relation 'stronger' is transitive... Every duel removes exactly one person from consideration. Thus, you can't find the strongest person with less than n-1 duels.