Re: large file support in diff utils

[Paul Eggert]

Chuck Swiger <address@hidden> writes:

> Paul Eggert wrote:
>> Chuck Swiger <address@hidden> writes:
>>> I mention this because I'd be curious to know what the memory and
>>> running time (big-O) of diff is.
>> That's discussed in the references, at least in theory.
>
> It's not in the manpage, and I didn't see anything in the info pages, either.
> Can you generalize off-hand?

Here's a quote from doc/diffutils.texi:

The basic algorithm is described
by Eugene W. Myers in ``An O(ND) Difference Algorithm and its Variations'',
@cite{Algorithmica} Vol.@: 1 No.@: 2, 1986, pp.@: 251--266; and in ``A File
Comparison Program'', Webb Miller and Eugene W. Myers,
@cite{Software---Practice and Experience} Vol.@: 15 No.@: 11, 1985,
pp.@: 1025--1040.
...
The algorithm was independently discovered as described by E. Ukkonen in
``Algorithms for Approximate String Matching'',
@cite{Information and Control} Vol.@: 64, 1985, pp.@: 100--118.