Time Bounds for Selection

By Manuel Blum, R. W. Floyd, V. Pratt, R. Rivest, Robert Endre Tarjan. 1973

The number of comparisons required to select the i-th smallest of n numbers is shown to be at most a linear function of n by analysis of a new selection algorithm-PICK. Specifically, no more than 5.4305 n comparisons are ever required. This bound is improved for extreme values of i, and a new lower bound on the requisite number of comparisons is also proved.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Generalized Byzantine-tolerant SGD (2018, methodology): “To obtian median values, there also exists an algorithm called selection algorithm (Blum et al., 1973) with average time complexity O ( n ) ( O ( n 2 ) in the worst case).”
From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification (2016, methodology): “(1)More elaborate O(K) algorithms exist based on linear-time selection (Blum et al., 1973; Pardalos & Kovoor, 1990).”
Incremental Off-policy Reinforcement Learning Algorithms (2017, background): “It only requires finding the ρnth order statistic and all the order statistics that are smaller, which can be computed in O(n) (Blum et al. 1973).”
A Fast Projection onto the Simplex and the l 1 Ball (2015, background): “If the pivot is the median of v, the complexity becomes O(N), which is optimal, but a linear time median finding routine, typically based on the median of medians [4], is cumbersome to implement and slow.”
Reducing the run-time complexity of multiobjective EAs: The NSGA-II and other algorithms (2003, methodology): “, and . is the time needed to find the median and call split on and . Using the algorithm of Blum et al.’s [ 6 ] this can be achieved in time . Recurrence relations similar to the one above were investigated by Monier in [22].”
Fast projection onto the simplex and the l1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\pmb {l}_\mathbf {1}$$\end{ (2015, background): “If the pivot is the median of v, the complexity becomes O(N), which is optimal, but a linear time median finding routine, typically based on the median of medians [11], is cumbersome to implement and slow.”
Learning with Confident Examples: Rank Pruning for Robust Classification with Noisy Labels (2017, methodology): “ples, ranked by predicted probability, via the BFPRT algorithm (Blum et al., 1973) in O(n) time, where n is”
Approximate counts and quantiles over sliding windows (2004, background): “The celebrated paper of Blum, Floyd, Pratt, Rivest and Tarjan[5], shows that selecting the kth largest element among N elements requires at least 1.”
Randomized selection on the GPU (2011, methodology): “The CLEAN algorithm is used in radio-astronomy to remove noise from images generated from multiple antennas, as shown in Figure 1.”
Phocas: dimensional Byzantine-resilient stochastic gradient descent (2018, methodology): “To do so, we use the so-called selection algorithm [3] with linear time complexity to ﬁnd the k th smallest element.”
Tracking the Best Linear Predictor (2001, background): “The median of a set of n numbers may be found in O(n) time (Blum et al., 1973).”
An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds (1990, methodology): “The algorithm relies on a routine such as that proposed in [ 2 ] for finding the exact median of a multiset in worst case linear time.”
The Algorithm Design Manual (2020, background): “[BFP72] proves that c · n suffice, but we want to know what c is.”
Divide and Conquer (2017, background): “Now, I claim that divide and conquer lets us compute all the evaluations A(1),A(w), .”