11
votes
Accepted
How to show that the median cannot be maintained in $O(1)$ time?
If you can maintain the median of $n$ objects in $O(1)$, then you can sort a sequence $x_1, \dots, x_n$ in $O(n)$:
first you compute a value $a$ smaller than all elements in the sequence and a value $...
- 685
1
vote
Accepted
Single-pass streaming quantile estimation using moments
Gan et al. address this in Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries. The answers are rather nuanced.
- 11k
Only top scored, non community-wiki answers of a minimum length are eligible