Minimum value in each row of an implicitly-defined totally monotone matrix

Given a totally monotone matrix $A$ whose entries $A[i, j]$ are implicitly defined by some function $f(i, j)$ (assume $f$ takes constant time to evaluate for all relevant $(i, j)$ ), determine the minimum value in each row.

Parameters

$m,n$ : dimensions of matrix; assume $m≥n$
possibly uses a function $f$ to define entries; assume evaluation of $f$ takes time $O(1)$

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 3 of 3 algorithms


SMAWK algorithm	1987	$O(n(1+\log(m/n)))$	$O(n)$
Divide and Conquer	1987	O(m*log(n))	O(log(n)) auxiliary
Naive algorithm	1940	$O(mn)$	$O(1)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms