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

Description

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

n, m: dimensions of matrix; assume m≥n

possibly uses a function f to define entries; assume evaluation of f takes time O(1)

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Naive algorithm	1940	$O(nm)$	$O({1})$ auxiliary	Exact	Deterministic
SMAWK algorithm	1987	$O(n({1}+log(n/m)$))	$O(n)$ auxiliary?	Exact	Deterministic	Time
Divide and Conquer	1987	$O(m*log(n)$)	$O(log(n)$) auxiliary?	Exact	Deterministic	Time

Time Complexity Graph

Space Complexity Graph

Time-Space Tradeoff