Analysis of An Approximate Median Selection Algorithm
Domenico Aldo Cantone, Viale A. Doria, Micha Hofri · Digital WPI · 2006
We present analysis of an efficient algorithm for the approximate median selection problem that has been rediscovered many times, and easy to implement. The contribution of the article is in precise characterization of the accuracy of the algorithm. We present analytical results of the performance of the algorithm, as well as experimental illustrations of its precision.