For the edit distance, a detailed survey of previous solutions can be found in [1]}, and here we only discuss the landmark results of the theoretical landscape. For the general variant of the problem, the first algorithm was given by Sellers [2]}. The algorithm was based on dynamic programming and used \(\mathcal {O}(nm)\)  time. Masek and Paterson [3]} improved the running time of the algorithm to \(\mathcal {O}(nm/ \log n)\)  via the Four Russians technique. On the lower bound side, it is known that there is no solution with strongly subquadratic time complexity unless the Strong Exponential Time hypothesis [4]} is false, even for the binary alphabet [5]}, [6]}.
Abboud et al. [7]} gave a more precise bound under a weaker assumption: Namely, they showed that even shaving an arbitrarily large polylog factor would imply that NEXP does not have non-uniform \(\mathrm {NC}^1\)  circuits. Finally, Clifford et al. [8]} showed that, in the cell-probe model with the word size \(w = 1\) , any randomised algorithm that computes the edit distances between the pattern and the text online must spend \(\Omega (\frac{\sqrt{\log n}}{(\log \log n)^{3/2}})\)  expected amortised time per character of the text.
