In Pijul, it is always O(log n + c), where c is the size of the largest conflict between the current repository and the patch you're trying to apply.
So, it is a double-exponential improvement in practical uses, even though you could totally make c = n for the sake of the argument.
The tradeoff is that Pijul doesn't handle the very cool (but rarely usable in practice) "darcs replace".
From an implementation perspective, Pijul is in Rust, relies on less external stuff than Darcs (for example no need for Putty on Windows), is available as a library.
edit: also, Pijul has branches, too, and Darcs doesn't. But branches are far from being as useful as in Git, and in fact most Git workflows use short-lived branches, which are essentially just patches in both Pijul and Darcs.