Take the 2-minute tour ×
Quantitative Finance Stack Exchange is a question and answer site for finance professionals and academics. It's 100% free, no registration required.

I'm hand rolling some visualization algorithms.

Extracting the min/max of a time series is $O(n)$, for n entries.

If I want the 25% and 75% mark, I could use an $O(n \log n)$ time sort, then get the 25% and 75% marks.

However, is there a way to do this in linear time?

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

Yes there is a way to find kth largest element in an unsorted list in linear time here. However, depending on what program you are using, implementing the algorithm might not increase performance. The built-in sort function is probably optimized in C, and hence is very fast.

share|improve this answer
    
Can't believe I forgot the genius that is Tarjan. –  user2936 Sep 20 '12 at 0:32
add comment

Your Answer

 
discard

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