0

To find the maximum and 4th Maximum of an array what is the minimum number of comparisons needed? I assume I have to use an algorithm similar to MinMax and the solution found here:

Find the 2nd largest element in an array with minimum number of comparisons\

But I'm not sure how i would adapt the tournament style to this scenario.

Community
  • 1
  • 1
bugdoctor9
  • 37
  • 3

1 Answers1

1

Interesting question...

I think the trick is just to run the tournament a 2nd time, but with the largest and 2nd largest removed from the set (as determined by tournament #1).

Tournament #1: To find in (1) [The largest] and in (2) [The 2nd largest]

Tournament #2: With (1) and (2) removed from the set. To find in (3) [The largest] and in (4) [The 2nd largest]. These will be the 3rd and 4th largest (respectively) from the original set.

  1. n - 1
  2. log n - 1
  3. (n-2) - 1
  4. log (n-2) - 1

[Edit]: I had better attempt some maths for completeness.

(1) + (2) + (3) + (4)

=> (n - 1) + (log n - 1) + ((n - 2) - 1) + (log (n-2) - 1)

=> 2n + (log n) + (log (n-2)) - 6

=> 2n + log (n^2 - 2n) - 6

Kuz
  • 96
  • 3