[darcs-users] darcs conflicts/dependencies -- is patch theory the place to start?

[Miles Gould]

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