DOIAbstract
AbstractLet X and Y be two sorted n-vectors and A = X + Y be an n×n matrix with sorted rows and columns such that aij=xi+yj. Let 1⩽k<n2. Vyskoč (1987) claimed that selecting the (k+1)st element of A could be done in O(logn) time if the kth element is known. In this note we prove that this result is not exact by showing that O(n) is a lower bound for the problem under Vyskoč's hypothesis. We also describe an O(n) algorithm and conclude by showing how the same algorithm can be used for searching on such matrices
Add to ORKG