Hirschberg's algorithm (Edit sequence, constant-size alphabet Sequence Alignment)
Jump to navigation
Jump to search
Time Complexity
$O(mn)$
Space Complexity
$O(n)$ words
(https://dl.acm.org/doi/10.1145/360825.360861)
Description
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
1975
Reference
http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/DynProg/Docs/Hirschberg-LCS-1975.pdf