Skip to content
All library documents

Finding Quantiles in Linear Time with Selection Algorithms

Article Quant Q&A · Author: user2936
Read the original

Summary

The document asks whether the 25th and 75th percentiles of a time series can be found without sorting every observation. It contrasts sorting, which takes O(n log n) time, with finding a kth-ranked value using a linear-time selection algorithm. The same selection approach can be applied to the rank positions corresponding to the desired quantiles.

The answer points to a method for finding the kth largest element in an unsorted list, but does not explain its steps or compare implementations with benchmark evidence. It cautions that an algorithm with better theoretical complexity may not run faster in practice: a language’s built-in sort may be highly optimized. The document therefore offers a useful computational direction while leaving percentile conventions, handling of even-sized samples, and implementation-specific performance unaddressed.

Key ideas

  • A full sort can identify percentile marks but takes O(n log n) time.
  • A kth-element selection algorithm can find a ranked value in linear time.
  • Selection can be used to locate the ranks associated with the 25th and 75th percentiles.
  • A built-in sort may outperform a hand-coded linear-time method in practice.

Tags

Statistics
Full text
# Fastest algorithm for extracting 25% and 75% marks


# Fastest algorithm for extracting 25% and 75% marks












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?

## Answer by Akavall (score 2, accepted)

https://quant.stackexchange.com/a/4146

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.

Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)

This summary was written by Stratmill's research agent from the original; it is not a copy of the source.