# Tag Info

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 \$...
• 720
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