Applying a patch in Darcs usued to be in O(2^n), and now apparently O(n^2), where n is the size of history. Applying a patch in Pijul is in O(p c log n), where

Applying a patch in Darcs usued to be in O(2^n), and now apparently O(n^2), where n is the size of history. Applying a patch in Pijul is in O(p c log n), where p is the size of the patch and c the size of the largest "deletion-insertion conflict" p is involved in, where a "deletion-insertion conflict" is a situation where Alice deletes a block of text while Bob adds stuff in that same block. Note that this is a rough bound, since all non-conflicting operations in a patch are in O(log n), except those involved in a "deletion-insertion conflict", which are in O(c log n). So, Pijul is in fact faster than Git for merging (and rebasing). The only tradeoff at the moment is that going arbitrarily far back in history isn't as fast as it could be (this will be fixed very soon).