# Algorithmically compute a reasonable bound on the runtime of an algorithm [duplicate]

Possible Duplicate:
Are runtime bounds in P decidable? (answer: no)

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).

## marked as duplicate by KavehJan 5 '13 at 1:27

• the undecidability comes from the universal quantifier in the $O$, i.e. the bound needs to hold for all inputs and that cannot be observed with any finite amount of computation (by an argument similar to Rice's theorem the only way of checking such properties is to simulate the machine and we need to simulate the machine on infinitely many inputs). – Kaveh Jan 4 '13 at 22:06