# Edit distance between all word pairs

Let there be a dictionary of M words with average length N. We want to compute an M×M matrix of edit distances between all word pairs.

Since there are M² word pairs, and the pairwise edit distance has O(N²) average time complexity, the upper bound on the average time complexity for our problem is O(M²N²).

Is there an upper bound tighter than O(M²N²) on the time complexity for our problem?

• Actaully, there is a recently found sub-quadratic algorithm for edit distance, with $O(N^{2-2/7})$ time complexity (approximation with a constant factor). Using this algorithm, the upper bound on your problem is lower- $O(N^{4-2/7})$. You can read about it here. – royashcenazi Jul 13 at 10:51
• @Apass.Jack You are correct, i mixed two different properties (the dictionary size M and the average word length N). The upper bound would then be O(M²N²). – Witiko Jul 13 at 12:48
• @royashcenezi Interesting. However, this is still a pointwise edit distance. I am mainly interested whether it is possible to improve the time complexity by computing distances for all word pairs in bulk. – Witiko Jul 13 at 12:50
• If you can find a fast approximation $E$ that never overestimates the edit distance you can speed up the search by using $E(x, y) \leq D(x, y) \leq \min_z \left[D(x,z) + D(z,y)\right]$ as lower and upper bounds. I doubt that's a worst-case improvement though. If $M$ and $N$ are massive or many strings are similar you can also get speedups by deduplicating work through tries. – orlp Jul 13 at 22:36