[darcs-users] Replacing the n^2 algorithm.

Anthony Towns aj at azure.humbug.org.au
Fri Jan 14 04:57:59 UTC 2005

Michael Conrad wrote:
> Aah, I'd been reading it wrong.  Actually, N^2 could also be a problem,
> depending on what N was.  (i.e. number of conflicts vs. number of patch
> units between conflicting units, etc)  Anyway, yes e^N is much worse,
> and I'm assuming now that N is number of conflicts?

N is the number of conflicting patches.

Say you have A1, A2, A3, A4, A5, etc all conflicting, and you pull them 
one at a time, in order.

Your initial repository is just A1, it's size is 1.
Your second repository is A1 + M(A1,A2), it's size is 1+(1+1).
Your third repository is A1 + M(A1,A2) + M(M(A1,A2),M(A1,A3)), it's size 
is 1+(1+1)+(1+1+(1+1)).

Your N+1 th repository is thus made up of the N patches that made up 
your N th repository, and an additionally patch which conflicts with 
every other patch in the repository, which is of the form:

	M( p_n-1, M( p_n-2, M( ... M( p_1, p_n ) ) ) ) )

But p_n-1 + ... + p_1 is what made up the N-1'th repository, so that 
patch alone is the size of the previous repository + 1 (for p_n).

So if S_i is the size of the ith repository, S_1=1, S_(i+1)=2(S_i)+1; 
and hence S_i=2^(i)-1. (Check: S_1=2^1-1=1; S_i+1=2(2^i)-1)+1=2^(i+1)-1)

That complexity is due to the representation of mergers -- the fact that 
p_n-1 above isn't just a "hunk ./foo 1234" patch, but is itself a merger 
of the preceeding patches.


More information about the darcs-users mailing list