# algorithm of determines the two largest of a series

i am trying to figure a algorithm problem that determines the two largest number of the a series of random 10 numbers. Thanks to your help.

-
You said a 'series' not a sequence or a list. Are there any known properties of this series? –  user2468 Dec 26 '10 at 0:28
If you mean series,please state whether we can assume that it have some specific properties,if it is sequence then change the question accordingly. –  Quixotic Dec 26 '10 at 10:25
does the algorithm need to perform in a specific way? Does it need to be < O(n lg n)? If not, just sort it the list and pick the last 2 elements. –  Sev Dec 26 '10 at 12:08
@Sev: you're joking, right? Tell me you're joking... –  TonyK Dec 26 '10 at 20:21
well, considering the form of the question, i was :) –  Sev Dec 26 '10 at 20:55

Just go through the list and keep track of the two largest numbers, that is have two variables that are the the two largest elements so far while going through.

-
And what would be the complexity for this approach ? –  Quixotic Dec 26 '10 at 10:39
@Debanjan, well there is constant work on each element (update two variables), so O(n), I guess you want to point out that the complexity rises when when we try to find the k largest element, then the complexity becomes O(k*n). However, the numbers where quite explicit here, 2 largest numbers among 10 elements, I guess the problem is that the question doesn't describe which one he wants. –  HaskellElephant Dec 26 '10 at 11:14
list = [random, random, random, ..., random]
largest := (list[0] > list[1]) ? list[0] : list[1]
secondlargest := (list[0] <= list[1]) ? list[0] : list[1]
for each num in list:
if num >= largest:
secondlargest := largest
largest := num
elseif num >= secondlargest:
secondlargest := num
return {largest, secondlargest}


You aren't going to be able to avoid iterating across the entire list because it is not sorted, and therefore you are going to have to search in $O(n)$ time. If the list is sorted, it becomes pretty much a non-problem, but there is no sense in sorting it if all you want is the two largest (if you have to do other things it might be worth it though)

-
If you're worried about running time, why don't you check the second condition first? If it fails, you can skip the first condition. –  TonyK Dec 26 '10 at 9:03
@TonyK: Because if the number you are checking is larger than the largest it will by definition be larger than the second largest. So say the largest is $10$ and the secondlargest is $9$, if you check against $11$ and do the second check first you would have largest as $10$ and secondlargest as $11$. Therefore to make it work properly, you would have to do another check within that one, which would defeat the point of the speedup (unless you could say that the data isn't really 'random', but was usually decreasing, such that the larger values would be found earlier). –  Reese Moore Dec 26 '10 at 16:18
Most of the data (if it's random) will be smaller than secondlargest. You can check this with one comparison. Your code uses two comparisons in these cases. –  TonyK Dec 26 '10 at 17:54
Oh: and why >= instead of > ? You're just making more work for yourself :-) –  TonyK Dec 26 '10 at 17:55

What you are looking for can be solved in $O(n)$.

This is called finding the k-th order statistic.The Wikipedia entry of Selection algorithm provides some insight.But probably a better discussion is presented in Chapter 9, Medians and Other statistics from Introduction to Algorithms, 2nd Ed.

Here is a well described randomized $O(n)$ approach : QuickSelect.

-
This is overkill if you want to find just the largest two. –  Aryabhata Dec 26 '10 at 18:22
I know but I can make tasks that will TLE any naive algorithm :-), in other cases I would rather do sort(v.rbegin().v.rend()); then display the v[0] and v[1] .In some cases say in interviews,most often we are supposed to present $O(n)$ algorithm since that is what that makes this task somewhat interesting. –  Quixotic Dec 27 '10 at 10:15

It might be worth noting that the naive way to find the $k$ largest elements requires $O(nk)$ operations, since updating the list of $k$ largest elements could take $O(k)$ operations. However, if these are stored in a heap then we get the better complexity $O(n \log k)$; this method is practical (i.e. actually outperforms the naive algorithm) for moderately sized $k$.

Edit: Debanjan's method shows how to solve this using $O(n + k\log k)$ operations, or $O(n)$ if we're not interested in the relative order of the $k$ largest elements. First you find the $k$th largest element using the classical $O(n)$ algorithm, and then you collect all elements at least as large as it is; if required, you then sort them.

-
A heap of two elements would be a big pessimisation! –  TonyK Dec 26 '10 at 9:01