Re: [bug-diffutils] time complexity of diff3

[Tim Roes]

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?

Thanks for you help, again,
Tim

--
Tim Roes
Herrmann-Leichtlin-Str. 30
D-76185 Karlsruhe

www.timroes.de

smime.p7s
Description: S/MIME Cryptographic Signature