Global taint tracking time complexity? about codeql HOT 5 CLOSED

The worst case time complexity is much much worse than what you suggest. It's polynomial at least, but it includes lots of additional factors, and #nodes is most definitely included. Another factor is #fields + #capturedvariables (which factors in worse than linearly). And virtual dispatch edges also play a role.
But fortunately we aren't really hitting the worst case, as we do lots of optimisations to improve the common case (without being able to completely shed the worst-case from a theoretical perspective). In the good case, I'd expect the total complexity to be about #nodes. The number of sources and sinks definitely play a role as well, but the average time complexity is actually, much better than a simple linear scaling there, because we can share a lot of flow reachability calculation between a set of sources and a set of sinks.

from codeql.

If I were to reduce the worst-case complexity to depend on just a single variable n being the size of the code base, then the complexity would be O(n^k) where k is just about 25, as far as I could count.

from codeql.

So that means if your code size grows 10 times bigger, there will be 10^25 more work?
Indeed, the worse case complexity is much much worse than I thought.

from codeql.

So that means if your code size grows 10 times bigger, there will be 10^25 more work?

Potential work in the worst case, yes, that's right (caveat, 25 might not be exactly right - it's a rough estimate based on a quick count). But again, the average case never really hits the worst case, so the typical experience is more like O(n).

Indeed, the worse case complexity is much much worse than I thought

Yes.

from codeql.

Actually, there are some safeguards in place, which I think might keep the worst-case bounded at O(n^7) instead of O(n^25). But the theoretical complexity doesn't really matter much in practice anyway.

from codeql.