---
OA_place: publisher
OA_type: gold
_id: '22915'
abstract:
- lang: eng
  text: "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?\r\nTo 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 \U0001D49C, there exists a graph G and an algorithm \U0001D49C' that,
    for all inputs I with G(I) ≅ G, is a factor O(log log n) faster than \U0001D49C.
    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."
acknowledgement: "Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann thank the
  VILLUM Foundation\r\ngrant (VIL37507) “Efficient Recomputations for Changeful Problems”
  for supporting this work.\r\nDaniel Rutschmann is supported by the European Research
  Council (ERC) under the European\r\nUnion’s Horizon 2020 research and innovation
  programme (No. 101019564) "
alternative_title:
- LIPIcs
article_number: '101'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Ivor
  full_name: Van Der Hoog, Ivor
  last_name: Van Der Hoog
- first_name: Eva
  full_name: Rotenberg, Eva
  last_name: Rotenberg
- first_name: Daniel P
  full_name: Rutschmann, Daniel P
  id: 7397d908-b582-11f0-bf73-88b902e86527
  last_name: Rutschmann
citation:
  ama: 'Van Der Hoog I, Rotenberg E, Rutschmann DP. Tight Better-Than-Worst-Case bounds
    for element distinctness and set intersection. In: <i>34th Annual European Symposium
    on Algorithms</i>. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2026. doi:<a href="https://doi.org/10.4230/LIPIcs.ESA.2026.101">10.4230/LIPIcs.ESA.2026.101</a>'
  apa: 'Van Der Hoog, I., Rotenberg, E., &#38; Rutschmann, D. P. (2026). Tight Better-Than-Worst-Case
    bounds for element distinctness and set intersection. In <i>34th Annual European
    Symposium on Algorithms</i> (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.4230/LIPIcs.ESA.2026.101">https://doi.org/10.4230/LIPIcs.ESA.2026.101</a>'
  chicago: Van Der Hoog, Ivor, Eva Rotenberg, and Daniel P Rutschmann. “Tight Better-Than-Worst-Case
    Bounds for Element Distinctness and Set Intersection.” In <i>34th Annual European
    Symposium on Algorithms</i>, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik, 2026. <a href="https://doi.org/10.4230/LIPIcs.ESA.2026.101">https://doi.org/10.4230/LIPIcs.ESA.2026.101</a>.
  ieee: I. Van Der Hoog, E. Rotenberg, and D. P. Rutschmann, “Tight Better-Than-Worst-Case
    bounds for element distinctness and set intersection,” in <i>34th Annual European
    Symposium on Algorithms</i>, L’Aquila, Italy, 2026, vol. 388.
  ista: 'Van Der Hoog I, Rotenberg E, Rutschmann DP. 2026. Tight Better-Than-Worst-Case
    bounds for element distinctness and set intersection. 34th Annual European Symposium
    on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 101.'
  mla: Van Der Hoog, Ivor, et al. “Tight Better-Than-Worst-Case Bounds for Element
    Distinctness and Set Intersection.” <i>34th Annual European Symposium on Algorithms</i>,
    vol. 388, 101, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a
    href="https://doi.org/10.4230/LIPIcs.ESA.2026.101">10.4230/LIPIcs.ESA.2026.101</a>.
  short: I. Van Der Hoog, E. Rotenberg, D.P. Rutschmann, in:, 34th Annual European
    Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.
conference:
  end_date: 2026-09-04
  location: L’Aquila, Italy
  name: 'ESA: European Symposium on Algorithms'
  start_date: 2026-08-31
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-13T22:01:52Z
date_published: 2026-08-25T00:00:00Z
date_updated: 2026-09-16T09:21:35Z
day: '25'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2026.101
ec_funded: 1
external_id:
  arxiv:
  - '2511.02954'
file:
- access_level: open_access
  checksum: c552853bfa37e4b9a0f060107e464ed0
  content_type: application/pdf
  creator: dernst
  date_created: 2026-09-16T09:20:49Z
  date_updated: 2026-09-16T09:20:49Z
  file_id: '22937'
  file_name: 2026_LIPIcsESA_vanderHoog.pdf
  file_size: 892322
  relation: main_file
  success: 1
file_date_updated: 2026-09-16T09:20:49Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2026.101
has_accepted_license: '1'
intvolume: '       388'
keyword:
- Comparison-based analysis
- set intersection
- universal optimality
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
  call_identifier: H2020
  grant_number: '101019564'
  name: The design and evaluation of modern fully dynamic data structures
publication: 34th Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '9783959774451'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: yes
title: Tight Better-Than-Worst-Case bounds for element distinctness and set intersection
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 388
year: '2026'
...