SMAWK algorithm ( Minimum value in each row of an implicitly-defined totally monotone matrix)

Time Complexity

$O(n({1}+\log(n/m)$))

Space Complexity

$O(n)$? words

(Need to keep track of which columns aren't pruned. Also uses $O(n)$ auxiliary space during prune-and-search?)

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

1987

Reference

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