'Time Complexity of the Damerau-Levenshtein Approximate String Matching Algorithm

I am currently doing some implementation work where I am talking through the upgrade of the standard Levenshtein algorithm to damerau-levenshtein by adding in transpositions as another Operation.

I understand that the time complexity of levenshtein given two strings of length m and n is O(mn), however I am unable to find any work describing if the addition of the fourth operation transposition changes this complexity at all.

Would anyone happen to know the answer, or could point me in the right direction?

Thanks

algorithmtime-complexitycomplexity-theorystring-matchingdamerau-levenshtein


Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source

Related Questions