TR04-085 Authors: Erez Petrank, Guy Rothblum

Publication: 5th October 2004 12:31

Downloads: 3469

Keywords:

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

findmedian.

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.