I strongly doubt that, just like a search in an unindexed database table is O(N) no matter whether you write it as an SQL query or a for loop.
What assumptions about dependencies does Nix make / weaken that makes resolution linear-time? Any of those 4 Russ Cox lists? Or did Nix come up with some genius insight that shows that there's more than 4 core assumptions in the NP Completeness proof and the 5th one is the one that can be safely dropped?