Altschul and Erickson (Edit sequence, local alignment Sequence Alignment)

Time Complexity

$O(mn)$

Space Complexity

$O(mn)$ words

(Uses a constant number of m*n arrays, whose contents are of size O(1))

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

1986

Reference

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