Complexity of selection in X+Y

DOI10.1016/0304-3975(89)90027-3MaRDI QIDQ1124333zbMATH OpenOpenAlexFDO

Authors S. H. Smith

Publication date 1989

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(89)90027-3

zbMATH Keywords

complexity of selectionlower bound

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Review text

The paper reviewed was inspired by the incorrect proposition by \textit{J. Vyskoč} [Theor. Comput. Sci. 51, 221-227 (1987; Zbl 0642.68072)] namely that for two sorted n-vectors X and Y selecting the \((k+1)\)-st element of \(A=X+Y\) can be done in 0(log n) time if the k-th element is known. The authors show by a simple counterexample that the proof of this claim is wrong and then they prove the lower bound \(\Omega\) (n) for this problem. Finally new 0(n) time algorithm for this type of selection problem is presented.

Recommendations

• Selection in \(X+Y\) and matrices with sorted rows and columns
• The complexity of searching in \(X+Y\) and other multisets
• scientific article; zbMATH DE number 3843148
• scientific article; zbMATH DE number 4026821
• A parallel selection algorithm

Cites work

• Lower Bounds for Selection in X + Y and Other Multisets
• Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $
• Selection in \(X+Y\) and matrices with sorted rows and columns
• Sorting X + Y

Cited in

(4)

• On space-efficient algorithms for certain NP-complete problems
• Optimal algorithms for generalized searching in sorted matrices
• Closing a long-standing complexity gap for selection: \(V _{3}(42) = 50\)
• The complexity of searching in \(X+Y\) and other multisets

This page was built for publication: Complexity of selection in \(X+Y\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1124333)