Jabarkan Perkiraan dari Jarak Levenshtein

Jarak Levenshtein antara dua string dengan panjang  dapat diperkirakan dalam faktor

di mana  adalah parameter bebas yang dapat diatur, dalam kompleksitas waktu .

Dapat dibuktikan bahwa jarak Levenshtein dari dua string dengan panjang  tidak dapat dihitung dalam waktu , untuk setiap ε yang lebih besar dari nol kecuali hipotesis strong exponential time salah.