Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.21202 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914310284902400 |
|---|---|
| author | Au, Andrew |
| author_facet | Au, Andrew |
| contents | This paper establishes the exact comparison complexity of finding an element repeated $n$ times in a $2n$-element array containing $n+1$ distinct values, under the equality-comparison model with $O(1)$ extra space. We present a simple deterministic algorithm performing exactly $n+2$ comparisons and prove this bound tight: any correct algorithm requires at least $n+2$ comparisons in the worst case. The lower bound follows from an adversary argument using graph-theoretic structure. Equality queries build an inequality graph $I$; its complement $P$ (potential-equalities) must contain either two disjoint $n$-cliques or one $(n+1)$-clique to maintain ambiguity. We show these structures persist up through $n+1$ comparisons via a "pillar matching" construction and edge-flip reconfiguration, but fail at $n+2$. This result provides a concrete, self-contained demonstration of exact lower-bound techniques, bridging toy problems with nontrivial combinatorial reasoning. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_21202 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Exact (n + 2) Comparison Complexity for the N-Repeated Element Problem Au, Andrew Data Structures and Algorithms This paper establishes the exact comparison complexity of finding an element repeated $n$ times in a $2n$-element array containing $n+1$ distinct values, under the equality-comparison model with $O(1)$ extra space. We present a simple deterministic algorithm performing exactly $n+2$ comparisons and prove this bound tight: any correct algorithm requires at least $n+2$ comparisons in the worst case. The lower bound follows from an adversary argument using graph-theoretic structure. Equality queries build an inequality graph $I$; its complement $P$ (potential-equalities) must contain either two disjoint $n$-cliques or one $(n+1)$-clique to maintain ambiguity. We show these structures persist up through $n+1$ comparisons via a "pillar matching" construction and edge-flip reconfiguration, but fail at $n+2$. This result provides a concrete, self-contained demonstration of exact lower-bound techniques, bridging toy problems with nontrivial combinatorial reasoning. |
| title | Exact (n + 2) Comparison Complexity for the N-Repeated Element Problem |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.21202 |