[pacman-dev] [patch] patch IV rewritten for git

Xavier shiningxc at gmail.com
Tue Jun 12 13:53:11 EDT 2007

I also find recursive algorithm more natural for recursive structure.
Maybe Nagy is the only one who doesn't :)
But as far as I can tell, this is a correct implementation of the topo
sort, so O(n+e) for the sort part. Did you also include the
computation of the edges, which is O(n^2), or is there something else
that I overlooked ?
This was already observed by Nagy here :

Though when I first looked at this part, I find it odd, because O(n^2)
shouldn't be needed there either, it's just a matter of :
for t in targets do
 for d in deps(t) do
  add(d, t.children)
But the problem is we don't have constant time access to the vertices.

More information about the pacman-dev mailing list