Finding modes with equality comparisons

We consider the comparison complexity of finding modes (the most frequently occurring elements) in a list of elements that are not necessarily from a totally ordered set. Here, the relation between elements is determined by equality comparisons whose outcome is = when the two elements being compared are equal, and ≠ otherwise. The problem generalizes the classical majority problem studied in this model (using equalities). We show that n 2 / 2 m − n / 2 comparisons are necessary and n 2 / m + n comparisons are sufficient to find an element that appears at least m times. This is in sharp contrast to the bound of Θ ( n log ⁡ ( n / m ) ) bound in the model where comparisons are <, =, > or ≤, >. We give three algorithms for finding mode, including one that is a generalization of a classical majority finding algorithm due to Fischer and Salzberg (1982) [9]. We also discuss upper and lower bounds for sorting (i. e. , finding the frequency of every element) and for finding the least frequent element. Sorting problem (under the equality comparisons) also known as equivalence class sorting, has applications in several scenarios where the total order of elements is either not possible or can not be revealed for security reasons.

Authors

• Varukumar Jayapaul
• J. Ian Munro
• Venkatesh Raman
• Srinivas Rao Satti

Keywords

• Mode finding
• Equality comparisons
• Turán's theorem
• Dirac's theorem
• Lower bound
• Adversary argument