[darcs-users] Need help getting off darcs

[David Roundy]

On Jan 3, 2008 6:44 PM, James D Sadler <james at jamesdsadler.com> wrote:
> I don't understand how patches having back references to their
> dependencies leads you to conclude that record would be O(N) and size
> of the repository O(N^2).  This is not a challenge, I am just missing
> the 'glue' that links my statements to your conclusion!

In general, the number of dependencies that need be stored for each
patch is O(N).  Thus the size of each patch is O(N) and the size of
the repository is O(N^2), the number of patches times the size of each
patch.  It would probably be common that patches would have many fewer
than N dependencies, but there are no guarantees of this, so in the
worst-case scenario, the repository size is O(N^2).

darcs record would need to compute the dependencies of the new patch.
Computing this would in general be O(N), since we'd need to check
whether or not it depends on N patches in the worst-case scenario.
When we're lucky, it might not be this expensive, but it certainly
could be.

David