SMAWK algorithm ( Minimum value in each row of an implicitly-defined totally monotone matrix)
Jump to navigation
Jump to search
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?)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
1987