On 18/09/12 12:09, Miles Gould wrote:
I *think* this means that the merge algorithm is
constant-time in the depth of patches that need merging.
A minute's extra thought convinces me that I was wrong about that.
Suppose we have
a-b-c-d-e-f-g
\
h-i-j-k-l-m
and want to merge them using pushouts. We must first compose the patches
c-d, ..., f-g and the patches h-i, ..., l-m and then take the pushout of
the two resulting composite patches. So in general, merging n patches
with m patches is O(n + m). But AIUI in Darcs, we have to commute every
patch in one branch past every patch in the other branch, so it's O(nm)
- is this right?
Miles
_______________________________________________
darcs-users mailing list
darcs-users@darcs.net
http://lists.osuosl.org/mailman/listinfo/darcs-users
