Complexity of selection in \(X+Y\) (Q1124333)

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.