The storage complexity of some estimators of the median (Q1316141)

The authors investigate the computational complexity of various procedures for finding the median of an unknown distribution from which independent random samples of any size can be drawn. They prove that the computation of the sample median of arbitrarily large samples requires storage of unbounded amounts of data. Precisely, they prove that even if the population consists of a known, finite number \(K\) of distinct elements, the computation of the medians of arbitrarily large samples requires \(K-1\) counters that need unbounded capacity, and no algorithm with either fewer counters or counters with bounded capacities can succeed. In contrast, an algorithm for computing a sequence of estimators (necessarily not sample medians) that converge almost surely to the median of any given (unknown) distribution and that requires only a small, fixed number of counters (to count certain events) and registers is introduced.