Search the biggest and second biggest number in O(n+logn) time

Question

Possible Duplicate:
Find the 2nd largest element in an array with minimum # of comparisom

May I know how to achieve searching the biggest and second biggest number in O(n+logn) time? Thank you in advance.

Best regards, Pidig

(that gives you n + O(log n) comparisons) – sdcvvc May 31 '12 at 14:39 — sdcvvc, May 31 '12 at 14:39
Did you mean O(n*logn) which can be done with a max-heap? – Justin May 31 '12 at 14:41 — Justin, May 31 '12 at 14:41

score 7 · Answer 1 · edited May 23 '17 at 12:24

Note that O(n+logn) = O(n), and iterating twice on the list is O(n).

Iterate once to find the max and remove/mark it,
Then iterating the second time to find the new max (second biggest element),

Because it iterate constant number of times on the array, the algorithm is O(n).

For general purpose k largest elements: You can do it using a min heap in O(nlogk), or selection algorithm in O(n) - as described in this answer, but for 2 greatest elements - these methods are overkill.

score 3 · Answer 2 · answered May 31 '12 at 14:51

I guess you mean n + log(n) - 2 comparisons.

Here is how you do it.

Compare elements in groups of two. i.e. make n/2 groups of two elements each.

Continue in this way with n/4, n/8, n/16 and so on till you get the first(largest) element.

Now the next largest element has to be amongst the losers of the first element in this method. Hence log(n) more comparisons for this.

Precisely this will take n + log(n) - 2 comparisons.

score 1 · Answer 3 · answered May 31 '12 at 14:38

1

You can actually do that in O(n) time: Selection Algorithm

answered May 31 '12 at 14:38

Jean Logeart

52,687
11
83
118

Search the biggest and second biggest number in O(n+logn) time

3 Answers3