Content deleted Content added
Correction: remove "pairs of" since more than 2 elements can hash to the same ___location |
m →Generalization: Finding repeated elements: typo: convoluted instead of convolute |
||
Line 26:
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
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 less comparisons than the order statistics algorithms.<ref name=bm/>
| |||