Divide and Conquer ( Minimum value in each row of an implicitly-defined totally monotone matrix)

Time Complexity

$O(m*log(n)$)

Space Complexity

$O(log(n)$) auxiliary? words

(Need to keep track of the specific indices where the minimums occur, up to depth log(n))

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

1987

Reference

https://link.springer.com/article/10.1007/BF01840359