> From: haskell-cafe-boun...@haskell.org > [mailto:haskell-cafe-boun...@haskell.org] On Behalf Of Ketil Malde > > Don Stewart <d...@galois.com> writes: > > > > http://hackage.haskell.org/package/Diff > > Wherein we can read: > > | This is an implementation of the O(ND) diff algorithm > [...]. It is O(mn) > | in space. > > At first I thought 'N' and 'M' would be the lengths of the lists, and > 'D' is the number of differences, but then the space bound > doesn't make > sense. I tried to find the reference, but Citeseer is down > (again. sigh). > > Anybody know what the bounds really are?
I think the space bounds are O(M+N). Section "4b. A Linear Space Refinement" concludes with "Unfortunately, the input sequences A and B must be kept in memory, implying that a total of O(M+N) space is needed." BTW, there is a minor improvement to this algorithm (claims to be faster, same space usage): http://research.janelia.org/myers/Papers/np_diff.pdf found via: http://scholar.google.com/scholar?q=%22An+O(NP)+Sequence+Comparison+Algo rithm.%22 I thought this paper was easier to understand. Alistair ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. ***************************************************************** _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe