Selection from Structured Data Sets
Erez Petrank, Guy N. Rothblum · Electronic colloquium on computational complexity · 2004
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 (n) n comparisons during preprocessing (before the rank j is provided) implies that select(j) must make at least (2 + )(n=e2 (n) ) comparisons in the worst case, where > 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 + )(n=e2 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 dierence 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.