> two almost-equal files. In that case the average running time should be way lower, no? Yes, indeed! What you're thinking of is "output-sensitive" algorithms

> two almost-equal files. In that case the average running time should be way lower, no? Yes, indeed! What you're thinking of is "output-sensitive" algorithms. There are some output-sensitive algorithms for edit distance. The fastest one I found is in "Improved Algorithms for Approximate String Matching" by Dimitris and Georgios Papamichail. They note: "We designed an output sensitive algorithm solving the edit distance problem between two strings of lengths n and m respectively in time O((s-|n-m|)min(m,n,s)+m+n) and linear space, where s is the edit distance between the two strings." http://arxiv.org/abs/0807.4368 http://arxiv.org/abs/0807.4368