Kth order statistic
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
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 |