Fall 2015: Theory Seminar
ICS, Room 209, 1:00pm
October 30, 2015:

Sorting and Selection with Equality Comparisons

Will Devanny

Abstract: We consider the fundamental sorting and selection problems on a list of elements that are not necessarily from a totally ordered set. Here relation between elements are determined by ‘equality’ comparisons whose outcome is = when the two elements being compared are equal and = otherwise. We determine the complexity of sorting (finding the frequency of every element), finding mode and other frequently occurring elements using only =,= comparisons. We show that Ω(n2/m) comparisons are necessary and this many 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 ≤, >.

Paper by Varunkumar Jayapul, J. Ian Munro, Venkatesh Raman, Srinivasa Rao Satti