The complexity of selection and ranking in X + Y and matrices with sorted columns

摘要

The complexity of selection is analyzed for two sets, X + Y and matrices with sorted columns. Algorithms are presented that run in time which depends nontrivially on the rank k of the element to be selected and which is sublinear with respect to set cardinality. Identical bounds are also shown for the problem of ranking elements in these sets, and all bounds are shown to be optimal to within a constant multiplicative factor.