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

$m,n$: 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(mn)$	$O({1})$	Exact	Deterministic
SMAWK algorithm	1987	$O(n({1}+\log(n/m)$))	$O(n)$?	Exact	Deterministic	Time
Divide and Conquer	1987	$O(m*log(n)$)	$O(log(n)$) auxiliary?	Exact	Deterministic	Time

Time Complexity Graph