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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s