3 ms·
> For a completely arbitrary program, it is not possible to calculate a tight bound on the time or memory complexity of that that program via static analysis. S
by User23 7y ago
> For a completely arbitrary program, it is not possible to calculate a tight bound on the time or memory complexity of that that program via static analysis. See Rice's Theorem[0].
That theorem proves that no general algorithm exists. That doesn’t mean it can’t be done for a particular program. The real challenge is that modern compilers and processors will execute in a way that is hard to predict from source code.
- edejong 7y agoThe question was whether it is hard to determine the space/time complexity of ‘a’ function, which firmly placed the question in Rice’s theorem grounds.