Tight Better-Than-Worst-Case bounds for element distinctness and set intersection

The element distinctness problem takes as input a list I of n values from a totally ordered universe, where pairwise comparisons between values are allowed, and the goal is to decide whether I contains any duplicates. It is a well-studied problem with a classical worst-case Ω(n log n) comparison-based lower bound by Fredman [TCS'76]. At first glance, this lower bound appears to rule out any algorithm more efficient than the naive approach of sorting I and comparing adjacent elements. However, upon closer inspection, the Ω(n log n) bound is overly pessimistic. For instance, if I contains n/2 identical elements, a median-finding algorithm will, regardless of the input order, find a duplicate in linear time. This raises a natural question: Are there comparison-based lower bounds for element distinctness that are sensitive to the amount of duplicates in the input instance? To address this question, we derive instance-specific lower bounds. For any input instance I, we represent the combinatorial structure of the duplicates in I by an undirected graph G(I) that connects identical elements. Each such graph G is a union of cliques, and we study algorithms by their worst-case running time over all inputs I' with G(I') ≅ G. We establish an adversarial lower bound showing that, for any deterministic algorithm 𝒜, there exists a graph G and an algorithm 𝒜' that, for all inputs I with G(I) ≅ G, is a factor O(log log n) faster than 𝒜. Consequently, no deterministic algorithm can be o(log log n)-competitive for all graphs G. We complement this with an O(log log n)-competitive deterministic algorithm, thereby obtaining tight bounds for element distinctness that go beyond classical worst-case analysis. Subsequently, we study the related problem of set intersection. We show that no deterministic set intersection algorithm can be o(log n)-competitive, and provide an O(log n)-competitive deterministic algorithm. We find it interesting and surprising to discover tight O(log log n)-competitive bounds for element distinctness. Moreover, we find the separation between element distinctness and the set intersection problem unexpected.