It is NP-hard, but realistically that should not be a concern for most dependency management questions users throw at it? Just how many variables are folks imagining are in a typical dependency tree?

Google claims the average number of dependencies is 35. My gut is most of these do not have too many versions, all told. Is this really big enough that you'd expect it to be the bottleneck?