Element distinctness problem: Difference between revisions

Revision as of 09:45, 21 April 2011

Revision as of 22:19, 17 May 2011

Line 23:

==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> J. Misra and D. Gries. Finding repeated elements. Sci. Comput. Prog., 2 (1982) 143-152. </ref>

The algorithm is a generalization of the one for a special case of ''k''=2, which had a rather convoluted history of publication.<ref name=bm>[[R.S. Boyer]], [[J. S. Moore]], "MJRTY - A Fast Majority Vote Algorithm," In R.S. Boyer (ed.), Automated Reasoning: Essays in Honor of Woody Bledsoe, Automated Reasoning Series, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1991, pp. 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/>

==References==