<p>The question you pose and the specific counting trick you describe is a classic one in program analysis. There is the theoretical problem of complexity analysis, and it's practical manifestation in terms of automatically estimating the performance of a piece of code. Such an automated analysis has several applications from detecting performance bugs to estimating the cost for some computation in the cloud.</p>

<p>Cody pointed out that the problem is undecidable in general. This problem is harder than proving termination, because obtaining a complexity bound entails that the program also terminates. There are two approaches to such a problem. One is from program analysis. The idea of adding a counter and estimating its value exists since the 70s. This encoding reduces the problem of determining running time to that of computing an invariant. </p>

<p>A second approach is to design a programming language that only admits programs of a certain bounded complexity. This is the area of <em>implicit computational complexity.</em> </p>

<p>Some references for both areas follow.</p>

<ol>
<li><a href="http://research.microsoft.com/en-us/um/people/sumitg/pubs/speed.html">The SPEED Project</a>, is one specific line of program analysis work that focuses on how to find bounds on counters once introduced into the program. The counters may measure time or space consumption.</li>
<li><a href="http://www.linta.de/~aehlig/university/pub/10-raml.pdf">Multivariate amortized resource analysis</a>, Jan Hoffman, Klaus Aehlig, Martin Hoffman, ACM TOPLAS 2012</li>
<li><a href="http://arxiv.org/abs/1005.0518v1">On Decidable Growth-Rate Properties of Imperative Programs</a>, Amir Ben Amram,  Developments in Implicit Computational complExity 2010. This is a beautiful line of work on bounding complexity of imperative programs by syntactic restrictions.</li>
</ol>

CC BY-SA 3.0
2012-12-08T10:03:38.143Z
2013-12-29T08:58:46.717Z
2013-12-29T08:58:46.717Z
Vijay D
<p>In general you cannot determine complexity, even for halting programs: let $T$ be some arbitrary Turing machine and let $p_T$ be the program (that always returns 0):</p>

<pre><code>input: n
run T for n steps
if T is in halting state, output: 0
otherwise, loop for n^2 steps and output: 0
</code></pre>

<p>It is clear that it is undecidable in general whether $p_T$ is linear-time or quadratic-time. </p>

<p>However, much work has been carried out on the effective computation of program complexity. I have particular fondness for <a href="http://lipn.univ-paris13.fr/~baillot/GEOCAL06/ICCworkshop.html" rel="nofollow">Implicit Complexity Theory</a> which aims at creating languages that, using special constructs or type disciplines, allows one to write only programs that inhabit a certain well-defined complexity class. By what I consider to be something of a miracle, these languages are often complete for that class!</p>

<p>One particularly nice example is described in <a href="http://hal.archives-ouvertes.fr/docs/00/59/18/53/PDF/effraie.pdf" rel="nofollow">this paper</a> by J.-Y. Marion, which describes a tiny imperative language, with a type discipline inspired from information-flow and security analysis techniques, which allows a characterization of algorithms in <strong>P</strong>.</p>

CC BY-SA 3.0
2012-09-14T20:25:19.650Z
As a side note, also see Epigram, which is a language which can guarantee termination.
Realz Slaw
CC BY-SA 3.0
2012-12-08T11:29:44.330Z
This is a nice start, but is there more to say? (For example, it seems to me that a given [elementary recursive function](http://en.wikipedia.org/wiki/ELEMENTARY)'s runtime must be straightforward to compute, yet such functions can solve any problem in the exponential hierarchy....)
usul
CC BY-SA 3.0
2012-12-08T21:21:34.760Z
Insofar as it is possible to determine that the input program is written in a restricted language, you can assume the time complexity is bounded by whatever upper bound that language imposes.  However, many primitive recursive functions have general recursive equivalents which are more efficient
Chris Pressey
CC BY-SA 3.0
2012-12-08T21:31:09.043Z
(accidentally saved that comment early, then exceeded the 5-minute limit.  The second sentence should read as follows:)  However, programs in these restricted languages may have equivalents in less restricted languages which are more efficient (specifically, many primitive recursive functions have general recursive equivalents which are more efficient) which, in practice, encourages the use of the unrestricted, harder-to-analyze languages.
Chris Pressey
CC BY-SA 3.0
2012-12-10T23:45:55.997Z
That's very interesting Chris! Do you have a reference? In fact it seems counter-inutitive: I would have suspected primitive recursive functions can simulate general recursive functions for a given number of steps, which would then limit the speedup to some constant factor.
cody
CC BY-SA 3.0
2012-09-12T21:57:40.623Z
2015-05-03T16:36:21.620Z
2015-05-03T16:36:21.620Z
cody
<p>The <a href="http://en.wikipedia.org/wiki/Halting_problem">Halting problem</a> states that it is impossible to write a program that can determine if another program halts, for <em>all possible input programs</em>. </p>

<p>I can, however, certainly write a program that can compute the running time of a program of  like:</p>

<pre><code>for(i=0; i&lt;N; i++)
    { x = 1; }
</code></pre>

<p>and return a time complexity of $N$, without ever running it. </p>

<p>For all other input programs, it would return a flag indicating it was unable to determine the time-complexity.</p>

<p>My question is this:</p>

<p><strong>What conditions must hold, such that we can algorithmically determine the time-complexity of a given program?</strong></p>

<p>*If there is a canonical reference or review article to this I would appreciate a link to it in the comments.</p>

CC BY-SA 3.0
2012-09-12T14:44:39.617Z
This question was initially posted to Stack Overflow, where it was suggested that it might not be an appropriate fit. It appears that this site is a better fit, but if it does not meet the minimum requirements of this Exchange please point me in the right direction.
Hooked
CC BY-SA 3.0
2012-09-12T14:53:55.987Z
(1) “The O-notation” does not mean “time complexity.”  (2) It is unclear what you mean by “O(infinity).”  Please avoid inventing a new notation if possible.  (3) Deciding whether a given program halts or not and giving an explicit upper bound on the time complexity of the program is different.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-12T15:04:26.807Z
@TsuyoshiIto (1) Please retag the question to what is appropriate (cc.complexity-theory?). (2) What is the `O(f)` for a program that never halts? Is the correct terminology that it doesn't exist? (3) I agree that determining if a program halts and stating an explicit bound are different questions, though I would be interested in both answers.
Hooked
CC BY-SA 3.0
2012-09-12T15:12:33.473Z
(1),(2): Your tag is correct; your usage of term “O-notation” is incorrect.  The _time complexity_ of a non-halting program can be said to be infinity, but do not use O(…) for that.  Please check any textbook in complexity theory.  (3) My point is that your question is unclear because you use nonstandard notation “O(infinity)” and you are mixing up two different questions.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-12T15:24:01.033Z
@TsuyoshiIto As you can tell, I'm not well-versed in the terminology (hence the posing of this question first on SO). Thank you for the helpful suggestions, I've tried to incorporate them in the following edit.
Hooked
CC BY-SA 3.0
2012-09-12T15:32:27.387Z
I am not familiar with inferring time complexity of programs in restricted classes, but one class of programs which may be worth checking for is called “bounded loop programs,” for which it is easy to bound the time complexity.  I remember that bounded loop programs are discussed in Chapter 3 of [Gems of Theoretical Computer Science](http://www.calvin.edu/~rpruim/publications/gems/) by Uwe Schöning and Randall J. Pruim in the context of deciding equivalence of two programs, but I am not sure how much relevant the chapter is to your question.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-12T19:14:50.077Z
I'm a little confused. In what way is this out of scope ? One reasonable answer to the OP's question would be language fragments (or even classes of fragments) for which running time can be determined algorithmically.
Suresh Venkat
CC BY-SA 3.0
2012-09-12T22:26:08.893Z
[suggest migrate to CS.SE]... to determine the complexity of a problem, you have to deal with infinite inputs, and no algorithm can do that, which you dont seem to realize with your example. however, there is a large field of _empirical analysis_ in CS of analyzing running times of programs on finite but "as large as possible" inputs. there is also a study of _semialgorithms_ or algorithms that do not return wrong answers but [conceptually] sometimes return with an answer "N/A"
vzn
CC BY-SA 3.0
2012-09-12T22:43:28.963Z
Related question: [Are runtime bounds in P decidable?](http://cstheory.stackexchange.com/q/5004/1037)
Artem Kaznatcheev
CC BY-SA 3.0
2012-12-08T10:08:34.090Z
I'm terribly late to this comment thread. We seem to pounce the moment a post smells newbie-ish. I'm not pointing fingers. I feel this instinct myself. Maybe we should be gentler. The OP admitted to not being familiar with the area or terms. What's the point of a question-answer site if we only tolerate people who know exactly what they want, and ask it in our language.
Vijay D
<computability><time-complexity><formal-methods><se.software-engineering>
To what extent can an algorithm predict the time complexity an arbitrary input program?
Hooked
# To what extent can an algorithm predict the time complexity an arbitrary input program?

(Asked by: username_0 on 2012-09-12)

The Halting problem states that it is impossible to write a program that can determine if another program halts, for all possible input programs. 
I can, however, certainly write a program that can compute the running time of a program of  like:
for(i=0; i
and return a time complexity of $N$, without ever running it. 
For all other input programs, it would return a flag indicating it was unable to determine the time-complexity.
My question is this:
What conditions must hold, such that we can algorithmically determine the time-complexity of a given program?
*If there is a canonical reference or review article to this I would appreciate a link to it in the comments.

**Tags:** computability, time-complexity, formal-methods, se.software-engineering
> **Comments:**
> **username_0**: This question was initially posted to Stack Overflow, where it was suggested that it might not be an appropriate fit. It appears that this site is a better fit, but if it does not meet the minimum requirements of this Exchange please point me in the right direction.  
> **username_1**: (1) “The O-notation” does not mean “time complexity.”  (2) It is unclear what you mean by “O(infinity).”  Please avoid inventing a new notation if possible.  (3) Deciding whether a given program halts or not and giving an explicit upper bound on the time complexity of the program is different.  
> **username_0**: @TsuyoshiIto (1) Please retag the question to what is appropriate (cc.complexity-theory?). (2) What is the `O(f)` for a program that never halts? Is the correct terminology that it doesn't exist? (3) I agree that determining if a program halts and stating an explicit bound are different questions, though I would be interested in both answers.  
> **username_1**: (1),(2): Your tag is correct; your usage of term “O-notation” is incorrect.  The _time complexity_ of a non-halting program can be said to be infinity, but do not use O(…) for that.  Please check any textbook in complexity theory.  (3) My point is that your question is unclear because you use nonstandard notation “O(infinity)” and you are mixing up two different questions.  
> **username_0**: @TsuyoshiIto As you can tell, I'm not well-versed in the terminology (hence the posing of this question first on SO). Thank you for the helpful suggestions, I've tried to incorporate them in the following edit.  
> **username_1**: I am not familiar with inferring time complexity of programs in restricted classes, but one class of programs which may be worth checking for is called “bounded loop programs,” for which it is easy to bound the time complexity.  I remember that bounded loop programs are discussed in Chapter 3 of [Gems of Theoretical Computer Science](http://www.calvin.edu/~rpruim/publications/gems/) by Uwe Schöning and Randall J. Pruim in the context of deciding equivalence of two programs, but I am not sure how much relevant the chapter is to your question.  
> **username_2**: I'm a little confused. In what way is this out of scope ? One reasonable answer to the OP's question would be language fragments (or even classes of fragments) for which running time can be determined algorithmically.  
> **username_3**: [suggest migrate to CS.SE]... to determine the complexity of a problem, you have to deal with infinite inputs, and no algorithm can do that, which you dont seem to realize with your example. however, there is a large field of _empirical analysis_ in CS of analyzing running times of programs on finite but "as large as possible" inputs. there is also a study of _semialgorithms_ or algorithms that do not return wrong answers but [conceptually] sometimes return with an answer "N/A"  
> **username_4**: Related question: [Are runtime bounds in P decidable?](http://cstheory.stackexchange.com/q/5004/1037)  
> **username_5**: I'm terribly late to this comment thread. We seem to pounce the moment a post smells newbie-ish. I'm not pointing fingers. I feel this instinct myself. Maybe we should be gentler. The OP admitted to not being familiar with the area or terms. What's the point of a question-answer site if we only tolerate people who know exactly what they want, and ask it in our language.  

---

## 2 answers

### Answer by username_6 on 2012-09-12. Score: 23 | Accepted answer

In general you cannot determine complexity, even for halting programs: let $T$ be some arbitrary Turing machine and let $p_T$ be the program (that always returns 0):
input: n
run T for n steps
if T is in halting state, output: 0
otherwise, loop for n^2 steps and output: 0

It is clear that it is undecidable in general whether $p_T$ is linear-time or quadratic-time. 
However, much work has been carried out on the effective computation of program complexity. I have particular fondness for Implicit Complexity Theory which aims at creating languages that, using special constructs or type disciplines, allows one to write only programs that inhabit a certain well-defined complexity class. By what I consider to be something of a miracle, these languages are often complete for that class!
One particularly nice example is described in this paper by J.-Y. Marion, which describes a tiny imperative language, with a type discipline inspired from information-flow and security analysis techniques, which allows a characterization of algorithms in P.

> **Comments:**
> **username_7**: As a side note, also see Epigram, which is a language which can guarantee termination.  
> **username_8**: This is a nice start, but is there more to say? (For example, it seems to me that a given [elementary recursive function](http://en.wikipedia.org/wiki/ELEMENTARY)'s runtime must be straightforward to compute, yet such functions can solve any problem in the exponential hierarchy....)  
> **username_9**: Insofar as it is possible to determine that the input program is written in a restricted language, you can assume the time complexity is bounded by whatever upper bound that language imposes.  However, many primitive recursive functions have general recursive equivalents which are more efficient  
> **username_9**: (accidentally saved that comment early, then exceeded the 5-minute limit.  The second sentence should read as follows:)  However, programs in these restricted languages may have equivalents in less restricted languages which are more efficient (specifically, many primitive recursive functions have general recursive equivalents which are more efficient) which, in practice, encourages the use of the unrestricted, harder-to-analyze languages.  
> **username_6**: That's very interesting Chris! Do you have a reference? In fact it seems counter-inutitive: I would have suspected primitive recursive functions can simulate general recursive functions for a given number of steps, which would then limit the speedup to some constant factor.  

---

### Answer by username_5 on 2012-12-08. Score: 11

The question you pose and the specific counting trick you describe is a classic one in program analysis. There is the theoretical problem of complexity analysis, and it's practical manifestation in terms of automatically estimating the performance of a piece of code. Such an automated analysis has several applications from detecting performance bugs to estimating the cost for some computation in the cloud.

Cody pointed out that the problem is undecidable in general. This problem is harder than proving termination, because obtaining a complexity bound entails that the program also terminates. There are two approaches to such a problem. One is from program analysis. The idea of adding a counter and estimating its value exists since the 70s. This encoding reduces the problem of determining running time to that of computing an invariant.

A second approach is to design a programming language that only admits programs of a certain bounded complexity. This is the area of *implicit computational complexity.*

Some references for both areas follow.

1. [The SPEED Project](http://research.microsoft.com/en-us/um/people/sumitg/pubs/speed.html), is one specific line of program analysis work that focuses on how to find bounds on counters once introduced into the program. The counters may measure time or space consumption.
2. [Multivariate amortized resource analysis](http://www.linta.de/~aehlig/university/pub/10-raml.pdf), Jan Hoffman, Klaus Aehlig, Martin Hoffman, ACM TOPLAS 2012
3. [On Decidable Growth-Rate Properties of Imperative Programs](http://arxiv.org/abs/1005.0518v1), Amir Ben Amram, Developments in Implicit Computational complExity 2010. This is a beautiful line of work on bounding complexity of imperative programs by syntactic restrictions.


---

