[bug-diffutils] time complexity of diff3

[Tim Roes]

Hi,

can anyone tell me what time complexity (linear, quadratic, cubic, ...) 
diff3 has?
The algorithm as it is described in [1] seems to have O(n^3).
Unfortunately I didn't found any information about that in any 
documentation (but might have missed it).

Thanks for your help,
Tim

[1] A formal investigation of Diff3 -- 
http://www.cis.upenn.edu/~bcpierce/papers/diff3-short.pdf

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

www.timroes.de

smime.p7s
Description: S/MIME Cryptographic Signature