Thanks for that explanation.

The algorithm is absolutely O(N*D)... worst case, which is what big-O notation means.  :-)  In the worst case the input consists of N unique elements, and the difference between A and B is B inserts a new element between each element of A.  This means we'll have an edit list of D = N/2, and HistogramDiff splits and recurses D times, with each recursion looking at N-2 elements from the higher level.

This doesn't happen often fortunately.  Even in our contrived DiffTestDataGenerator we don't see this sort of input.  In the contrived test data we have a number of unique elements that can be hashed and located efficiently (since they are just primitive char).  Because there is no fallback, we only match on the common low-occurrence elements, which are quickly found in the hashtable.  Because there are so few of these, D is practically constant, and our run time during this test probably behaves more like O(N) time.

The more that I think about it, the more that I'm uncertain we should even have this test.  We don't really change MyersDiff that often.  Testing for algorithm correctness is sufficient.  If we are really meddling with the algorithm, we should be running it against real data sets like linux-2.6.git to see if there is a performance difference on real-world inputs, not contrived cases.  Our DiffAlgorithm implementations are designed to run well on human written source code.  They are designed to run no worse than O(N * D) on all inputs.  The latter I'm willing to prove theoretically rather than rely on a benchmark.  The former can only be well established by periodically running the tests over some real-world corpuses that people actually care about.

So I think I'll try to write a new test program similar to TextHashFunctions, but to exercise our DiffAlgorithms instead of line-level hash routines.