3 ms·
But in the worst case, initializing one package causes the count in each of the remaining packages to update. Maybe they have a clever way of doing that. Or may
by rcme 3y ago
But in the worst case, initializing one package causes the count in each of the remaining packages to update. Maybe they have a clever way of doing that. Or maybe this is very unlikely to happen in practice.
- morelisp 3y agoIf you take n as packages (vertices) you can have n² dependencies (edges), each of which needs to be looked at once no matter what. So if you count that way n² is unavoidable in any dependency sorting. (Usually for such algorithms I see n = |v| + |e|, or max(|v|, |e|), or just left as |v| and |e|.)