Finding the highest 2 numbers- computer science

Question

I'm trying to figure out an algorithm to find the highest 2 numbers in a list of numbers.

The highest number can be found in n-1 stages, perhaps by doing the fist step of a bubble sort or something along those lines. To me it seems that finding the next highest number as well could be found in a total of 1.5n comparisons on average.

My professor set us homework to write an alogrithm that finds the highest 2 numbers in n + log(n) comparisons. Is this even possible? Any ideas, suggestions?

Edit: When I say n + log(n) I'm not referring to O(n + log n), but rather exactly n + log n

Answer 1

Yes, it's possible to do it in no more than (n + log n). I really can't tell you how without giving away the answer, but let me try. :-)

Take the n numbers, compare them in pairs at a time. Take the ceil(n/2) "winners", and repeat, "like a binary tree". Questions: how many comparisons does it take to find the largest one? How many people does this "winner" win against? To whom might the second largest have lost? So how many comparisons does it now take to find the second largest number?

The answer turns out to be a total of n-1 + ceiling(log n) - 1 comparisons, where the log is to base 2. You can also prove using an adversarial argument that it is not possible to do better than this in the worst case.

Answer 2

Edit: Oops, missed a simple thing due to stupidity. This solution isn't correct, although I am keeping it here as it is still avg(n+log(n)). Thanks to ShreevatsaR for pointing out my stupidity. I did consider the tree search, but completly missed the idea of backtracking to find the second highest number in log(n).

Anyway, here follows my proof for why the inferior algorithm is no more than avg(n+log(n)). In real life it should still perform pretty well at least.

• First compare against the second highest recorded number.
• Only if that comparison succeeds, compare against the highest recorded number.

To prove that it is on average n+log n, we simply have to prove that the first comparison only succeeds log(n) times on average. And that is fairly simple to see or demonstrate.

1. Assume P as the the actual position of the current second largest number in a sorted version of the list, and run the algorithm
2. If P>2 then when a larger number is found, the new P will on average be no more than P/2.
3. If P=2 then the first comparison can not succeed, as there is no number that is greater than the current second largest number.
4. P can at most equal N
5. From 2, 3 and 4 it should be trivial to see that the first comparison can not succeed more than log(N) times on average.