Keep m counters. Hit → increment. New + free slot → count 1. New + full → replace the min slot with count = min+1, recording error = min.
| Operation | Time | Note |
|---|---|---|
| Hit (increment) | O(1) | move to adjacent bucket |
| Miss, free slot | O(1) | count-1 bucket |
| Miss, evict min | O(1) | head bucket (Stream-Summary) |
| Miss, evict (naive) | O(m) | min-scan |
| Report top-k | O(m log m) | sort the slots |
| Space | O(m) | independent of stream length |