Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR04-085 | 3rd October 2004 00:00

Selection from Structured Data Sets


Authors: Erez Petrank, Guy Rothblum
Publication: 5th October 2004 12:31
Downloads: 3403


A large body of work studies the complexity of selecting the
$j$-th largest element in an arbitrary set of $n$ elements (a.k.a.
the select$(j)$ operation). In this work, we study the
complexity of select in data that is partially structured by
an initial preprocessing stage and in a data structure that
is dynamically maintained. We provide lower and upper
bounds in the comparison based model. For preprocessing, we show
that making at most $\alpha(n) \cdot n$ comparisons during
preprocessing (before the rank $j$ is provided) implies that select$(j)$ must make at least $(2 + \epsilon)({n}/{e 2^{\alpha(n)}})$ comparisons in the worst case, where $\epsilon > 2^{-40}$.

For dynamically maintained data structures, we show that if
the amortized number of comparisons executed with each insert operation is bounded by $i(n)$, then select$(j)$
must make at least $(2 + \epsilon)({n}/{e 2^{i(n)}})$ comparisons
in the worst case, no matter how costly the other data structure
operations are. When only insert is used, we provide a lower
bound on the complexity of findmedian. This lower bound is
much higher than the complexity of maintaining the minimum, thus
formalizing the intuitive difference between findmin and

Finally, we present a new explicit adversary for comparison based
algorithms and use it to show adversary lower bounds for selection
problems. We demonstrate the power of this adversary by improving
the best known lower bound for the findany operation in a
data structure and by slightly improving the best adversary lower
bound for sorting.

ISSN 1433-8092 | Imprint