What is the time complexity of edit distance (levenshtein)?

Worst case O(m × n). Space complexity is O(m × n), or O(min(m,n)) with rolling rows.

Edit distance (Levenshtein)

medium

Up is a deletion, left an insertion, diagonal a replacement - free when the characters match. The traceback turns the number into an actual edit script.

Worst O(m × n)Space O(m × n), or O(min(m,n)) with rolling rows

Loading the edit distance (levenshtein) engine…

Where to go next

Longest common subsequence

medium

Match means diagonal; mismatch means the better of two.

Longest increasing subsequence

medium

The O(n²) table, and the O(n log n) trick that replaces it.

KMP pattern matching

hard

The text pointer never moves backwards.