Finding two largest elements in an array

This is a very interesting problem indeed.

The problem comes in multiple flavors:

  • Find two largest elements in an array in 1.5n comparisons.
  • Find two largest elements in an array in n+log(n)−2 comparisons.
  • Prove that no algorithm for finding two largest elements in an array can do this in less than n+ log (n)−2 comparisons.
  • What is the fastest algorithm for finding three largest elements?

 

References:

Code:

Advertisements