Kth order statistic
Revision as of 11:57, 10 October 2022 by Admin (talk | contribs) (Created page with "== Problem Description== the kth order statistic of a statistical sample is equal to its kth-smallest value. == Bounds Chart == 1050px == Step Chart == 1050px == Improvement Table == {| class="wikitable" style="text-align:center;" width="100%" !width="20%" | Complexity Classes !! width="40%" | Algorithm Paper Links !! width="40%" | Lower Bounds Paper Links |- | rowspan="1" | Exp/F...")
Problem Description
the kth order statistic of a statistical sample is equal to its kth-smallest value.
Bounds Chart
Step Chart
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 |