Are runtime bounds in P decidable? (answer: no)
Originally asked on SO: https://stackoverflow.com/questions/13371025
I have seen many questions asking if this computation is possible, but they all ask about writing a program to compute the complexity of arbitrary algorithms (which is obviously undecideable). I am willing to make the following restrictions on the input:
The algorithm terminates The algorithm is purely functional
The question is, can a program be written to compute the time complexity of such an algorithm through static analysis? If the input algorithm does not terminate, the program behaviour is undefined (it may crash, return a lie, or fail to terminate).