Item — HN Reader

Is the upper bound

  O( <number of words> * <max word length> ^2 )

correct ? It seems to me that the upper bound should be

  O(<number of words> * <max word length>) ^2

Looks like a typo.

In fact there is another fairly simple optimization one can make if one is interested only in computing the distance, but not interested in the actual edit sequence. If you look at the algorithm for filling up the table you will see you refer only to the previous row. So one can work with just two consecutive rows, thereby substantially reducing the space complexity, but not the time complexity unfortunately.

The time complexity can however be reduced on average to O(n * d), where n is the length of the longer word and d is the edit distance between the two words, this optimization is by Ukkonen. There have been other optimizations since then. The best I believe gives a time complexity of O(n + d^2)

The consecutive row optimisation is an interesting one and in practice, it has a large impact on the runtime, even though the theoretical time complexity does not change.

Having a smaller table => it can fit in the cache => better temporal locality of reference => faster runtime.

Very true. Those fast matrix and linear algebra libraries: BLAS, LAPACK are fast not because of using different algorithms but because of optimizing for cache reuse. Its the same reason why sometimes binary search trees performs better than (unoptimized) hash tables.