<blockquote>
  <p><strong>Possible Duplicate:</strong><br>
  <a href="https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no">Are runtime bounds in P decidable? (answer: no)</a>  </p>
</blockquote>



<p>Originally asked on SO: <a href="https://stackoverflow.com/questions/13371025">https://stackoverflow.com/questions/13371025</a></p>

<p>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:</p>

<p>The algorithm terminates
The algorithm is purely functional</p>

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

CC BY-SA 3.0
2013-01-04T21:58:01.793Z
This is already answered [here](http://cstheory.stackexchange.com/q/5004/186). I am going to close this as a duplicate since that seems to answer your question.
Kaveh
CC BY-SA 3.0
2013-01-04T22:04:44.413Z
Your question is a little bit vague since you don't explain what is a "reasonable" bound, however a similar argument would show that the problem is undecidable for any definition I can think of. The restrictions won't matter as long as the class of programs you are considering is capable of syntactically checking if a given string is a terminating computation of a given Turing machine on blank tape (which is a very simple task that any reasonable class of program would be expected to perform unless it is a really very restricted class),
Kaveh
CC BY-SA 3.0
2013-01-04T22:06:36.603Z
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
CC BY-SA 3.0
2013-01-04T22:16:15.460Z
@Kaveh thanks!  I should have asked over here in the first place :)
singpolyma
<time-complexity>
Algorithmically compute a reasonable bound on the runtime of an algorithm
singpolyma
# Algorithmically compute a reasonable bound on the runtime of an algorithm

(Asked by: username_0 on 2013-01-04)

> **Possible Duplicate:**  
> [Are runtime bounds in P decidable? (answer: no)](https://cstheory.stackexchange.com/questions/5004/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).

**Tags:** time-complexity
> **Comments:**
> **username_1**: This is already answered [here](http://cstheory.stackexchange.com/q/5004/186). I am going to close this as a duplicate since that seems to answer your question.  
> **username_1**: Your question is a little bit vague since you don't explain what is a "reasonable" bound, however a similar argument would show that the problem is undecidable for any definition I can think of. The restrictions won't matter as long as the class of programs you are considering is capable of syntactically checking if a given string is a terminating computation of a given Turing machine on blank tape (which is a very simple task that any reasonable class of program would be expected to perform unless it is a really very restricted class),  
> **username_1**: 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).  
> **username_0**: @Kaveh thanks!  I should have asked over here in the first place :)  

---

## 0 answers

