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?

  • 1
    $\begingroup$ 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. $\endgroup$ – royashcenazi Jul 13 at 10:51
  • $\begingroup$ @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²). $\endgroup$ – Witiko Jul 13 at 12:48
  • $\begingroup$ @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. $\endgroup$ – Witiko Jul 13 at 12:50
  • $\begingroup$ 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. $\endgroup$ – orlp Jul 13 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.