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

{{DISPLAYTITLE:Minimum value in each row of an implicitly-defined totally monotone matrix (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 == 

{| class="wikitable sortable"  style="text-align:center;" width="100%"

! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference

|-

| [[Naive algorithm ( Minimum value in each row of an implicitly-defined totally monotone matrix)|Naive algorithm]] || 1940 || $O(mn)$ || $O({1})$ || Exact || Deterministic ||  
|-
| [[SMAWK algorithm ( Minimum value in each row of an implicitly-defined totally monotone matrix)|SMAWK algorithm]] || 1987 || $O(n({1}+\log(n/m)$)) || $O(n)$? || Exact || Deterministic || [https://link.springer.com/article/10.1007/BF01840359 Time]
|-
| [[Divide and Conquer ( Minimum value in each row of an implicitly-defined totally monotone matrix)|Divide and Conquer]] || 1987 || $O(m*log(n)$) || $O(log(n)$) auxiliary? || Exact || Deterministic || [https://link.springer.com/article/10.1007/BF01840359 Time]
|-
|}

== Time Complexity Graph == 

[[File:Minimum value in each row of an implicitly-defined totally monotone matrix - Time.png|1000px]]