My Favorite Algorithm: Linear Time Median Finding (2018)
Linear-time algorithms for finding medians and order statistics spark both admiration and skepticism, as developers weigh their elegant theory against practical performance and implementation complexity. Commenters compare classic quickselect and median-of-medians to more advanced variants (e.g., Floyd–Rivest, Alexandrescu’s work), explore streaming and approximate quantile estimators like t-digest and Greenwald–Khanna for massive or unbounded data, and highlight when guarantees on worst‑case runtime truly matter. Along the way, they touch on related topics such as radix sorting for strings, interview practices that demand reproducing advanced algorithms under time pressure, and how asymptotic complexity often diverges from what’s actually fastest in real systems.
Linear-Time Selection Algorithms
- Discussion centers on quickselect vs. deterministic median-of-medians (BFPRT) and variants like Floyd–Rivest and introselect.
- Several note that median-of-medians is elegant but has large constants; often slower than randomized quickselect unless inputs are huge or worst-case guarantees matter.
- Others point to newer work (e.g., Alexandrescu-style selection, practical benchmarks and libraries) that make deterministic selection competitive in practice.
- Some mention specialized optimizations when selecting extreme quantiles (e.g., biased pivots, “j-th of k-th”, Floyd–Rivest-style tweaks).
Radix Sort and String / Integer Sorting
- Debate over whether radix sort is “O(kN)” or “O(N+M)” for strings; one side defines M as total character count, making it linear in input size.
- Practical comments: radix sort can be extremely fast, especially for fixed-size integers or strings, but comparison sorts often win on CPUs unless N is large or k is small.
- Links to optimized parallel/string radix sorts and cutting-edge variants; concern over recursion depth and cache behavior for MSD vs LSD approaches.
Streaming and Approximate Quantiles
- Many references to online median/quantile estimators: remedian, p², FAME, Greenwald–Khanna, t-digest, histogram-based methods (log/exponential, HDR, ddsketch, hg64).
- Tradeoffs discussed: memory bounds, quantile vs value error, stationary vs rolling quantiles, relative vs absolute error, and applicability to anomaly detection and monitoring.
- Some note that approximations are often “good enough”, especially in observability systems; others emphasize hard questions about error bounds and assumptions.
Interviews and Real-World Constraints
- Multiple stories of interview questions about medians of huge streams or files; criticism that expected “optimal” heap or selection algorithms are unrealistic in 30 minutes.
- Suggestions of simpler multi-pass or radix/bucket-style solutions for 32-bit integers under tight memory or streaming constraints.
- Strong skepticism about “PhD-level” whiteboard questions, with some arguing they select for leetcode practice rather than job-relevant skills.
Complexity, Proofs, and Big-O Nuances
- Several alternative proofs that median-of-medians recurrence is O(n), including superadditivity and induction-based bounds.
- Discussion of average vs worst-case quickselect behavior, the effect of skewed distributions, and whether using the mean as pivot helps (often not).
- Philosophical notes: theoretical CS cares about problems and bounds; existence of an O(n) algorithm changes research focus even if the first such algorithm is impractical.
- Side debate on big-O vs real-world limits: in practice all programs on finite machines are O(1), but big-O remains useful for understanding scaling.
Implementation Details and Miscellany
- Nitpicks about the article’s Python code (float vs integer division, variable naming) and about claiming small-n fallbacks as “constant time”.
- Explanation of why groups of 5 are used in BFPRT and how groups of 3 or 4 can be adapted while keeping linear complexity.
- Related “favorite algorithms” mentioned: alias method for O(1) weighted sampling and parallelizable merge techniques.