Complexity of selection in \(X+Y\)

DOI10.1016/0304-3975(89)90027-3zbMath0678.68034OpenAlexW1986665918MaRDI QIDQ1124333

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

lower boundcomplexity of selection

Mathematics Subject Classification ID

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

Related Items (3)

Optimal algorithms for generalized searching in sorted matrices ⋮ The complexity of searching in \(X+Y\) and other multisets ⋮ On space-efficient algorithms for certain NP-complete problems

Cites Work

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

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