Quantitative Finance Stack Exchange is a question and answer site for finance professionals and academics. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
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

Your Answer

 
discard

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