Another way to look at it is that in practice N is typically bounded by a large constant, making the time complexity effectively O(1).
For dependency resolution specifically, the set of possible dependencies is probably in the range 100 - 10000 for all ecosystems, even if the number of available packages in an ecosystem continues to grow.
10000?
Wait until you meet pip and liberal requirements.txt
And then you encounter packages with `setup.py` that generates a random list of dependencies on each run. You can't know the dependencies without running code.