Complexity of selection in \(X+Y\)
type: Item
instance of: scholarly article
title: Complexity of selection in \(X+Y\)
zbMATH Open document ID: 0678.68034
DOI: 10.1016/0304-3975(89)90027-3
author: S. H. Smith
published in: Theoretical Computer Science
publication date: 1989-01-01T00:00:00Z
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.
reviewed by: Jozef Vyskoč
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68P10
zbMATH DE Number: 4112007
zbMATH Keywords: complexity of selection
zbMATH Keywords: lower bound
MaRDI profile type: MaRDI publication profile
full work available at URL: 0304-3975(89)90027-3
OpenAlex ID: W1986665918
cites work: Sorting X + Y
cites work: Lower Bounds for Selection in X + Y and Other Multisets
cites work: Selecting the Kth Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $
cites work: Selection in \(X+Y\) and matrices with sorted rows and columns
Recommended article: Selection in \(X+Y\) and matrices with sorted rows and columns
Recommended article: The complexity of searching in \(X+Y\) and other multisets
Recommended article: Q3313271
Recommended article: Q3768394
Recommended article: A parallel selection algorithm
description: scientific article; zbMATH DE number 4112007