Content deleted Content added
m Reverted edits by 93.206.41.241 (talk) to last version by David Eppstein |
m Open access bot: hdl, doi added to citation with #oabot. |
||
Line 38:
|bibcode=
|doi=10.4086/toc.2005.v001a003
|doi-access=free
}}</ref> and Kutin<ref>
{{cite journal
|last1=Kutin |first1=S.
Line 48 ⟶ 49:
|bibcode=
|doi=10.4086/toc.2005.v001a002
|doi-access=free
}}</ref> independently (and via different proofs) extended his work to obtain the lower bound for all functions.
==Generalization: Finding repeated elements==
Elements that occur more than ''n''/''k'' times in a multiset of size n may be found in time O(''n'' log ''k''). The element distinctness problem is a special case of ''k''=''n''. This algorithm 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|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>
| |||