Well, the actual complexity of apply and unrecord is O(p c log h), where p is the size of the patch, c the size of the largest conflict in which p is involved, and h is the size of history. That makes Pijul perfectly usable, even on large repositories.