Minimum value in each row of an implicitly-defined totally monotone matrix: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
Line 26: | Line 26: | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:Minimum value in each row of an implicitly-defined totally monotone matrix - Time.png|1000px]] | [[File:Minimum value in each row of an implicitly-defined totally monotone matrix - Time.png|1000px]] | ||
== Space Complexity | == Space Complexity Graph == | ||
[[File:Minimum value in each row of an implicitly-defined totally monotone matrix - Space.png|1000px]] | [[File:Minimum value in each row of an implicitly-defined totally monotone matrix - Space.png|1000px]] | ||
== Pareto | == Pareto Frontier Improvements Graph == | ||
[[File:Minimum value in each row of an implicitly-defined totally monotone matrix - Pareto Frontier.png|1000px]] | [[File:Minimum value in each row of an implicitly-defined totally monotone matrix - Pareto Frontier.png|1000px]] |
Revision as of 14:04, 15 February 2023
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
n, m: 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(nm)$ | $O({1})$ auxiliary | Exact | Deterministic | |
SMAWK algorithm | 1987 | $O(n({1}+log(n/m)$)) | $O(n)$ auxiliary? | Exact | Deterministic | Time |
Divide and Conquer | 1987 | $O(m*log(n)$) | $O(log(n)$) auxiliary? | Exact | Deterministic | Time |