# 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 & \text{if i<m/2}\\ j & \text{if i=m/2}\\ Half(i-1,j) & \text{if i>m/2 and Edit(i,j) = Edit(i-1,j)+1}\\ Half(i,j-1) & \text{if i>m/2 and Edit(i,j) = Edit(i,j-1)+1}\\ Half(i-1,j-1) & \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) & \text{if m\le 1}\\ O(m) & \text{if n\le 1}\\ O(mn) + \max_h \left( T(m/2,h) + T (m/2, n−h)\right) & \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.)

• Because I missed this when Dan asked me on my qualifying exam, that's why. – Jeffε Sep 1 '12 at 15:09
• i remember having this as a (guided) exercise and thinking it was pretty cool – Sasho Nikolov Sep 1 '12 at 17:29

The algorithm you describe that runs in space $O(n_1 + n_2)$ actually recovers the final edit, and the state just before the final edit. So if you run this algorithm $O(n_1 + n_2)$ times, you can recover the entire edit sequence, at the expense of increasing the runtime. In general, there is a time-space trade-off which is controlled by the number of rows you retain at the time. The two extreme points of this trade-off are space $O(n_1n_2)$ and space $O(n_1+n_2)$, and between these, the product of time and space is constant (up to big O).