Re: [bug-diffutils] time complexity of diff3

[Jim Meyering]

Tim Roes wrote:
> On 05/29/2012 04:24 AM, Paul Eggert wrote:
>> I don't see why. I'd guess diff3 is O(n**2) but have not done an analysis.
>
> That seems also more reasonable to me. I am writing a paper explaining
> diff3 in every step
> for university at the moment based on the mentioned paper. I changed
> some ways, how
> I describe the algorithm and ended up with O(n^2), but I am pretty
> sure the original paper
> has O(n^3) [so I might be still mistaken]. I guess O(n^2) is then the
> real complexity of
> the algorithm.
>
> And just another small question, if you would be so kind to help me there :-)
> The man page of diff3 states out that it is written by Randy Smith. In
> the repository
> there is none commit by a person with that name, but you commited quite much.
> Did you commit some work for him?

Also note that the people doing the earliest work either did not
use version control or never told us how to find their repository.