Myers promises to run in O(N * D), where N is the sum of the lengths of A and B, and D is the size of the minimum edit script.  I don't think this is true for the current PatienceDiff implementation.

In particular there is a sorting step during each recursion.  But if I'm thinking it through correctly, PatienceDiff's running time should be bounded by the size of the inputs, around O(A log A + B log B + D) =~ O(N log N + D).  That matches with a variation of Myers' algorithm that uses suffix trees.

I _think_ O(N log N + D) is going to be faster than O(N * D), but if N is really big, log N could easily exceed D.  :-)