Row Minima For Free

All row minima of a totally monotone $r \times c$ matrix accessed implicitly through a cost function, in $O((r+c)\log(r+c))$ evaluations, which is $n \log n$ for a square matrix. Divide and conquer on rows, solving the middle row first, is what achieves it.

All row minima of a totally monotone $r \times c$ matrix accessed implicitly through a cost function, in $O(c(1 + \log(r/c)))$ evaluations, which is linear for a square matrix. Total monotonicity means no $2 \times 2$ submatrix has its two row minima on opposite diagonal corners.

All row minima of an arbitrary $r \times c$ matrix accessed implicitly through a cost function, in $O(rc/\log c)$ evaluations, which is sublinear in the matrix size. Word-parallel comparison of packed rows is what removes the logarithmic factor.

The single global minimum of a totally monotone $r \times c$ matrix accessed implicitly through a cost function, in $O(\log r \log c)$ evaluations, which is logarithmic for a square matrix. Total monotonicity means every row's minimum sits weakly right of the row above.