Content deleted Content added
→Generalization: Finding repeated elements: fixed typo Tag: Reverted |
Undid revision 1264526708 by 37.244.251.1 (talk) uncorrect. More than one time is more than n/n times, not more than n/2 times. |
||
Line 61:
==Generalization: Finding repeated elements==
{{main|Misra–Gries heavy hitters algorithm}}
Elements that occur more than <math>n/k</math> times in a multiset of size <math>n</math> may be found by a comparison-based algorithm, the [[Misra–Gries heavy hitters algorithm]], in time <math>O(n\log k)</math>. The element distinctness problem is a special case of this problem where <math>k=
==See also==
| |||