I’ve been talking about the diff algorithm for three weeks now, and I’m proud to say that I now own the phrase “stupid diff” (at least as far as Google cares, which is all that really matters anyway). I think I’ll start putting a little trademark symbol after it.

[**Update, 19 Apr 2005:** Only a day after I posted this, and I’m no longer the #1 Google result for “stupid diff”. Oh well. Easy come, easy go.]

At this point, I’ve presented all the parts and pieces needed to make a serviceable Longest Common Subsequence algorithm. Now let’s look at just how serviceable. How efficient are these parts and pieces?

Last time, I said we’d reached polynomial time. But what degree polynomial are we talking about? Here’s a quick sketch of what the algorithm does:

- Loop through all the elements in A, and for each A
_{i}:- Loop through all the elements in B, and for each B
_{j}that matches A_{i}:- Loop through all the CSes we have so far, and for each CS that we can construct a longer CS from by appending [i, j]:
- Loop through all the CSes
*again,*calling Expendable on [CS_{k}, CS_{new}] and discarding CSes as needed.

- Loop through all the CSes

- Loop through all the CSes we have so far, and for each CS that we can construct a longer CS from by appending [i, j]:

- Loop through all the elements in B, and for each B

Looks like our algorithm, so far, is O(N^{4}). Sure beats our old super-exponential time, but N^{4} still leaves something to be desired.

Can we do better? You bet. In fact, by the time we’re done, the limiting factor is going to be how efficiently we can find matches: those outer two loops. Next time, I’ll take a look at making that a little more efficient (though still technically O(N^{2})), and start setting the stage for some of the later improvements.