Complexity of selection in \(X+Y\) (Q1124333)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4112007
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Complexity of selection in \(X+Y\) |
scientific article; zbMATH DE number 4112007 |
Statements
Complexity of selection in \(X+Y\) (English)
0 references
1989
0 references
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.
0 references
complexity of selection
0 references
lower bound
0 references
0.7882592082023621
0 references
0.7838122248649597
0 references
0.7448960542678833
0 references
