Automated computation of algorithm time complexity for terminating algorithms
big-o, code-analysis, computer-science, halting-problem, time-complexity
Solution
I finally asked in the right place, and got the answer. No.
https://cstheory.stackexchange.com/questions/14969/algorithmically-compute-a-reasonable-bound-on-the-runtime-of-an-algorithm#comment40524_14969
Problem
There are a lot of related questions here on SO, 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).