To devise a proper algorithm to calculate unrestricted Damerau–Levenshtein distance note that there always exists an optimal sequence of edit operations, where once-transposed letters are never modified afterwards. (This holds as long as the cost of a transposition, formula_18, is at least the average of the cost of an insertion and deletion, i.e., formula_19.) Thus, we need to consider only two symmetric ways of modifying a substring more than once: (1) transpose letters and insert an arbitrary number of characters between them, or (2) delete a sequence of characters and transpose letters that become adjacent after deletion. The straightforward implementation of this idea gives an algorithm of cubic complexity: formula_20, where "M" and "N" are string lengths. Using the ideas of Lowrance and Wagner, this naive algorithm can be improved to be formula_21 in the worst case, which is what the above pseudocode does.