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 summaryheavy hitters algorithm]], in time <math>O(n\log k)</math>. The element distinctness problem is a special case of this problem where <math>k=n</math>. This time is optimal under the [[decision tree model]] of computation.<ref>{{citation|first1=J.|last1=Misra|first2=D.|last2=Gries|author2-link=David Gries|title=Finding repeated elements|journal=Science of Computer Programming|volume=2|year=1982|issue=2|pages=143–152|doi=10.1016/0167-6423(82)90012-0|hdl=1813/6345|hdl-access=free}}.</ref>
