Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a list of $2n$ elements, we have to find the $n$'th largest element. Which is the best algorithm (Time complexity + comparison) for this particular problem?

I know that this could be solved in general by sorting or by finding finding the k-th order statistic. But I am looking for something way simpler than k-th order statistic which solves this particular problem due to the $2n$ and $n$'th restriction.

Hurrah!! Problem is solved!

Thanks,

share|improve this question
1  
"Typical approaches... (are) not something that I am looking for." - then, what? It's not too hard to adapt methods for finding the median... –  J. M. Aug 1 '12 at 2:50
    
There is a list of sorting algorithms on Wikipedia ; I don't know anything about sorting, but I think you should at least take the time to read and study it yourself : en.wikipedia.org/wiki/Sorting_algorithm –  Patrick Da Silva Aug 1 '12 at 2:51
    
Thanks J.M. Now I know how to solve this one :) –  AlgoFreak Aug 1 '12 at 2:57
    
Remove the largest element, and you're finding the median. There is a "well-known" linear-time algorithm for that. –  Robert Israel Aug 1 '12 at 2:58
    
Also stackoverflow.com/questions/1054802/… –  user2468 Aug 1 '12 at 3:08
add comment

2 Answers

Use the median of medians algorithm to find the median in linear time. This is the best possible since all elements must be examined. It is interesting for a number of reasons: it violates the intuition that sorting is the fastest way to accomplish this, it is an optimal algorithm for the median problem and problems with optimal algorithms are rare, and also it calls into question the zero-one-infinity rule by dividing the list into fifths or smaller parts (thirds yields a log-linear algorithm, like sorting). Recently I mentioned this algorithm as an anecdote about the number $5$ itself.

share|improve this answer
add comment

Why not sort? Just comparing the $2n$ elements to anything will take $O(n)$ time, and it's easy to see that all $2n$ elements will have to be compared to something. To sort it takes only $O(n\ln n)$ time, worst-case.

EDIT As Robert Israel pointed out, one can find the median in $O(n)$ time. In fact, the selection algorithm can find the $k^{th}$ smallest element in $O(n)$ time. Learn something new everyday.

share|improve this answer
1  
But finding the median can be done in $O(n)$. –  Robert Israel Aug 1 '12 at 2:59
1  
...and of course, there are methods for finding the median that don't need a preliminary sorting. –  J. M. Aug 1 '12 at 3:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.