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