Алгоритм расстояния Левенштейна лучше, чем O (n * m)?

Я искал расширенный алгоритм расстояния Левенштейна, и лучшее, что я нашел до сих пор , это O (n * m), где n и m - длины двух струн. Причина, по которой алгоритм находится в таком масштабе, заключается в пространстве, а не во времени, с созданием матрицы из двух строк, таких как эта:

Есть ли в открытом доступе алгоритм Левенштейна, который лучше, чем O (n * m)? Я не прочь посмотреть документы и исследования по передовой информатике, но не смог ничего найти. Я нашел одну компанию, Exorbyte, которая предположительно создала сверхсовременный и сверхбыстрый алгоритм Левенштейна, но, конечно, это коммерческая тайна. Я создаю приложение для iPhone, в котором хотел бы использовать расчет расстояния Левенштейна. Доступна реализация objective-c , но с ограниченным объемом памяти на iPod и iPhone я хотел бы найти лучший алгоритм, если это возможно.