Kth order statistic

From Algorithm Wiki
Revision as of 10:46, 21 September 2021 by Yashsherry (talk | contribs) (→‎Bounds Chart)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Problem Description

the kth order statistic of a statistical sample is equal to its kth-smallest value.

Bounds Chart

Kth order statisticBoundsChart.png

Step Chart

Kth order statisticStepChart.png

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic
Quadratic
nlogn Naive Selection (1940)
Linear Hoare's Selection Algorithm (QuickSelect) (1961)
Hashing (1940)
logn