3 ms·

Is it just me or is the new import initialization algorithm n^2 in the worst case? Surprised by that.

• morelisp 3y ago
  That's just the easy specification of the algorithm, it's implemented by a heap and counter on each package so I assume it's more like n lg n.
  • 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 ago
      If 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|.)