On Jan 3, 2008 6:44 PM, James D Sadler <[EMAIL PROTECTED]> 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 _______________________________________________ darcs-users mailing list [email protected] http://lists.osuosl.org/mailman/listinfo/darcs-users
