Linear Space Algorithm

A Linear Space Algorithm is an algorithm whose algorithm space complexity can be bounded by a linear function.

• • …
• Counter-Example(s):
  • a Polynomial Space Algorithm.
  • a Linear Time Algorithm.
• See: Maximal Common Subsequence.

---

---

References

1975

• (Hirschberg, 1975) ⇒ Daniel S. Hirschberg. (1975). “A Linear Space Algorithm for Computing Maximal Common Subsequences.” In: Communications of the ACM, 186).

---