# How can you compute the expected edit distance in $O(2^{3n/2})$ time?

In a coding challenge an answer claimed to be able to compute the expected edit distance between two binary strings of length $$n$$ in $$O(2^{3n/2})$$ edit distance calculations by dynamic programming. A naive solution would requite $$O(2^{2n})$$ edit distance calculations.

The answer gives optimized code but no mathematical or algorithmic explanation. I cannot see how to achieve the claimed complexity. How is this possible?

Heh…for the record, all I said was that the time seems to scale as approximately $$\tilde O(2^{1.5n})$$. If this was anything more than a conjecture based on the timing data that I included in the post, I would have said something more specific!

I’m sure you’re familiar with the usual Wagner–Fischer algorithm for Levenshtein distance, where we compute $$d_{i,j} = d(a_{[0, i)}, b_{[0, j)})$$ based on $$a_{i-1}, b_{j-1}, d_{i-1,j-1}, d_{i-1,j}, d_{i,j-1}$$. From there, my algorithm is based on two observations.

Firstly, each column $$d_{*,j}$$ is a function of the previous column $$d_{*,j-1}$$, the string $$a$$, and the bit $$b_{j-1}$$. We iterate over all strings $$a$$ (modulo symmetries), but instead of iterating over all strings $$b$$, we map each possible column $$d_{*,j-1}$$ to the two possible columns $$d_{*,j}$$, storing the collection of possible columns in a hash map with a counter for duplicates. This allows us to deduplicate some work when many different prefixes $$b_{[0, j)}$$ lead to the same column $$d_{*,j}$$.

Secondly, using a separate dynamic programming algorithm, we can precompute an upper bound $$w_{i,j}$$ on $$d(a_{[i, n)}, b_{[j, n)})$$ based only on $$a$$. Then, given a column $$d_{*,j}$$, the final distance $$d_{n,n}$$ can never be more than $$m = \min_i (d_{i,j} + w_{i,j})$$, so we can replace each $$d_{i,j}$$ with $$\min \{d_{i,j}, m - |i - j|\}$$ without affecting the final result. This lets us recognize more columns as duplicates and deduplicate more work.

• Combining identical columns is a neat idea -- how much computation does it save? E.g., what are the values of nDistinctColsAtPos[i] / 2^i? – j_random_hacker Feb 3 at 20:46

I didn't try reading the source code there, but here is one way to achieve $$O(2^{3n/2})$$ edit distance computations (but NOT $$O^*(2^{3n/2})$$ time overall).

Let's define $$D(a, b)$$ as the Levenshtein edit distance between two strings $$a$$ and $$b$$ -- that is, the minimum number of single-character insertions, deletions or substitutions required to turn one into the other. Let $$a = cd$$. Then there is some $$e$$ and $$f$$ such that $$b = ef$$ and $$D(a, b) = D(c, e) + D(d, f)$$. That is, regardless of how we split $$a$$ into two parts, there is a way to split $$b$$ into two parts so that the edit distances of corresponding pairs sum to the original edit distance. Moreover, of all the ways of splitting $$b$$ into $$e$$ and $$f$$, the one(s) that produce a minimum total value for $$D(c, e) + D(d, f)$$ are the one(s) that give you the true value of $$D(a, b)$$. (You can always get an alignment of $$a$$ to $$b$$ by placing the alignment of $$c$$ to $$e$$ next to the alignment of $$d$$ to $$f$$, so clearly no partition can result in a distance lower than $$D(a, b)$$ -- that would imply an alignment of $$a$$ to $$b$$ with lower distance than the lowest possible distance.)

Assuming $$n$$ is even, it's enough to precompute a table $$T(x, y)$$ that gives the edit distance for every pair of binary strings $$(x, y)$$ in which $$|x| = n/2$$ and $$|y| \le n$$. (Note that even though we let $$y$$ have any length up to $$n$$ here, this is not so bad: there are only twice as many binary strings of length up to $$n$$ as there are binary strings of length exactly $$n$$.) We can then compute the distance between any pair of length-$$n$$ binary strings $$(a, b)$$ in $$O(n)$$ time as follows:

$$D(a, b) = \min_i(T(a[1 \dots n/2], b[1 \dots i]) + T(a[n/2 + 1 \dots n], b[i+1 \dots n])$$

I haven't thought much about the case where $$n$$ is odd -- in the worst case, you might need a DP matrix twice the size, one to hold the answer for all pairs of strings $$(a, b)$$ in which $$|a|=\lfloor n/2 \rfloor$$ and one for $$|a|=\lceil n/2 \rceil$$. But I think it can be handled with less work than that.

The approach I'm suggesting here still involves $$O^*(2^{2n})$$ steps, since it still considers each pair of length-$$n$$ strings, but cuts the number of edit distance computations down to $$O^*(2^{3n/2})$$. Each of these computations still takes $$O(n^2)$$ time. Overall it takes $$O(2^{3n/2}n^2 + 2^{2n}n) = O(2^{2n}n)$$ time and $$O(2^{3n/2})$$ space. Note that this is faster than the naive $$O(2^{2n}n^2)$$ algorithm by a factor of $$n$$ -- but due to the space usage, it's probably not usable above about $$n=20$$.

• Looking at the running times which increase by roughly 3 for each increased n, do you think this can be what they did? – fomin Jan 25 at 16:36
• I can't tell what their code is doing. But the times they give are cumulative, so it looks to me more like a factor of 2 for each increase in $n$. – j_random_hacker Jan 25 at 17:51
• A factor of 2 seems better than either your algorithm or $2^{3n/2}$ unless I am mistaken...? – fomin Jan 25 at 21:52
• Yes, much better! I suggest just asking them for more information. – j_random_hacker Jan 26 at 8:05
• They were asked in the comments but haven't replied. – fomin Jan 26 at 8:56