12 Jun
2007
12 Jun
'07
5:53 p.m.
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 : http://archlinux.org/pipermail/pacman-dev/2007-April/008135.html 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.