hide
Free keywords:
-
Abstract:
This paper shows that finding the row minima (maxima) in an
$n \times n$ totally monotone matrix in the worst case requires
any algorithm to make $3n-5$ comparisons or $4n -5$ matrix accesses.
Where the, so called, SMAWK algorithm of Aggarwal {\em et al\/.}
finds the row minima in no more than $5n -2 \lg n - 6$ comparisons.
