2008/06/20 by Ryan J. Tibshirani, Tibshirani, Ryan J. · 1 voice · 28 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Applications (stat.AP) #Complexity and Algorithms in Graphs #Computation #Computation (stat.CO) #Computer science #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Data set #FOS: Computer and information sciences #Mathematics #Running time #Set (abstract data type) #Statistics #cs.DS #stat.AP #stat.CO
paper · pdf · doi:10.48550/arxiv.0806.3301
published in arXiv (Cornell University) (Cornell University) · 14 pages, 1 Postscript figure
openalex publication_date 2008/06/20 · arxiv published 2008/06/20 · arxiv created 2009/05/12 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
This paper describes a new median algorithm and a median approximation algorithm. The former has O(n) average running time and the latter has O(n) worst-case running time. These algorithms are highly competitive with the standard algorithm when computing the median of a single data set, but are significantly faster in updating the median when more data is added.