Tag
order-statistics
- Apr 30, 2026 Median-of-Medians and the Deterministic Linear Selection Bound Why grouping into fives makes the pivot provably good, how the recurrence resolves to a linear bound, and why the constant keeps it out of hot paths. algorithms
- Dec 5, 2025 Quickselect and the Cost of Finding One Element in Place How the selection recursion differs from quicksort, why the expected cost is linear, and which inputs make the linear promise fail. algorithms
- Sep 11, 2024 Order-Statistic Augmentation and Rank Queries How a subtree count maintained through every rotation answers rank and select in logarithmic time, and why the aggregate must be recomputable from children alone. data structures
- Apr 28, 2024 Quantiles from Finite Samples and Their Confidence Bands What a p99 computed from a few hundred observations actually estimates, how the order statistic maps to a binomial interval, and why tail claims need sample sizes that frequently do not exist. performance engineering