Find items with frequency > n/k using only k−1 counters — watch the decrement-all step
| Operation | Cost | Note |
|---|---|---|
| Process one item (avg) | O(1) | hash lookup + increment/claim |
| Decrement-all (worst per item) | O(k) | touches all k−1 counters; ≤ n/k times total |
| Whole pass | O(n) | amortized over the stream |
| Space | O(k) | fixed, independent of distinct count |
| Naive exact counting | O(distinct) | full hash map — blows up memory |