Space complexity to compute the optimal string alignment for the Levenshtein edit distance If we are given two strings of size $n_1$ and $n_2$, the standard Levenshtein edit distance computation is by a dynamic algorithm with time complexity $O(n_1 n_2)$ and space complexity $O(n_1 n_2)$. (Some improvements can be made as a function of the edit distance $d$, but we make no assumption on $d$ being especially small.) If you are only interested in the value of the edit distance (i.e., the minimal number of edits), a well-known improvement of the usual algorithm (where you only keep the previous and current row of the alignment table) reduces the space complexity to $O(\max(n_1, n_2))$.

However, if you want to get the actual edits of an optimal edit script, is it possible to do better than $O(n_1 n_2)$ memory usage, possibly at the expense of running time?
There is no need for the tradeoff that Yuval suggests.  The entire optimal editing sequence can be computed in $O(nm)$ time and $O(n+m)$ space, using a mixture of dynamic programming and divide-and-conquer first described by Dan Hirschberg.  (A linear space algorithm for computing maximal common subsequences.  Commun. ACM 18(6):341–343, 1975.)

Intuitively, Hirschberg's idea is to compute a single editing operation halfway through the optimal edit sequence, and then recursively compute the two halves of the sequence.  If we think of the optimal edit sequence as a path from one corner of the memoization table to the other, we need a modified recurrence to record where this path crosses the middle row of the table.  One recurrence that works is the following:

$$
Half(i,j) = \begin{cases}
   \infty &amp; \text{if $i&lt;m/2$}\\
   j &amp; \text{if $i=m/2$}\\
   Half(i-1,j) &amp; \text{if $i&gt;m/2$ and $Edit(i,j) = Edit(i-1,j)+1$}\\
   Half(i,j-1) &amp; \text{if $i&gt;m/2$ and $Edit(i,j) = Edit(i,j-1)+1$}\\
   Half(i-1,j-1) &amp; \text{otherwise}
\end{cases}
$$

The values of $Half(i,j)$ can be computed at the same time as the edit distance table $Edit(i,j)$, using $O(mn)$ time.  Since each row of the memoization table depends only on the row above it, computing both $Edit(m,n)$ and $Half(m,n)$ requires only $O(m+n)$ space.



Finally, the optimal editing sequence transforming the input strings $A[1..m]$ into $B[1..n]$ consists of the optimal sequences transforming $A[1 .. m/2]$ into $B[1 .. Half(m, n)]$ followed by the optimal sequence transforming $A[m/2 + 1 .. m]$ into $B[Half(m, n) + 1 .. n]$.  If we compute those two subsequences recursively, the overall running time obeys the following recurrence:
$$
T(m,n) = \begin{cases}
  O(n) &amp; \text{if $m\le 1$}\\
  O(m) &amp; \text{if $n\le 1$}\\
  O(mn) + \max_h \left( T(m/2,h) + T (m/2, n−h)\right)  &amp; \text{otherwise}
\end{cases}
$$
It's not hard to prove that $T(m,n) = O(mn)$.  Similarly, since we only require space for one dynamic-programming pass at a time, the total space bound is still $O(m+n)$.  (The space for the recursion stack is negligible.)