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 summary]], 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 algorithmtime 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>
The algorithm is a generalization of the one for a special case of ''k''=2 (the [[Boyer–Moore majority vote algorithm]]), which had a rather convoluted history of publication.<ref name=bm>{{citation|first1=R. S.|last1=Boyer|author1-link=Robert S. Boyer|first2=J S.|last2=Moore|author2-link=J Strother Moore|contribution=MJRTY - A Fast Majority Vote Algorithm|editor-first=R. S.|editor-last=Boyer|title=Automated Reasoning: Essays in Honor of Woody Bledsoe|series=Automated Reasoning Series|publisher=Kluwer Academic Publishers|___location=Dordrecht, The Netherlands|year=1991|pages=105–117}}.</ref>
The above algorithms rely only on the test of identity of the elements. If sorting is allowed, previously known [[order statistics]] finding algorithms may be exploited. For example, for ''k''=2, a [[median]] may be found first in [[linear time]], and then it may be easily tested whether there are more than ''n''/2 median elements. However the above algorithms require fewer comparisons than the order statistics algorithms.<ref name=bm/>
