3
$\begingroup$

I think of an algorithm which computes the time complexity. It would be great if a code editor could compute the time complexity of the selected lines and even compare two pieces of codes in order to help developer to select one of them. I heard something related with halting problem but couldn't figure out.

$\endgroup$
3
$\begingroup$

It would be great, wouldn't it? And like most problems regarding Turing Machines (or "algorithms"), there is no such algorithm, and there never will be:

Consider for example the language $$\{M: M\text{ is a TM that runs in time }O(n^3)\}$$ It is quite easy to reduce the halting problem to this language. Indeed, given input $M,w$ for the halting problem, the reduction outputs a machine $K$ that given input $x$, runs $M$ on $w$, and accepts $x$ iff $M$ halts on $w$, and does not halt otherwise. Since running $M$ on $w$ takes constant time (if it halts at all), then $K$ runs in time $O(n^3)$ iff $M$ halts on $w$.

Thus, it is undecidable (not in $coRE$, to be exact). There is nothing special about $n^3$, the same reduction works easily for every function greater than $n\log n$ (below $n\log n$ things get a bit more involved).

Also, the Halting problem itself can be regarded as a sort of "run-time problem", in the sense that you don't even ask what the runtime of an algorithm is, but just whether it halts. Even that is undecidable.

It is interesting to note that the language, as formulated in this answer, is also not in $RE$, it is an easy exercise to show it. However, if you replace the $O(n^3)$ with exactly $n^3$, then the problem is in $coRE$. Then, the former reduction needs certain adjustments, but the problem is still undecidable.

$\endgroup$
  • $\begingroup$ The idea I became here is, let's say I have 100 lines of code and I put a breakpoint at line 10. It executes the code line by line from line 10 to 100. Maybe it would execute it for the worst case and tell us the complexity between that lines. $\endgroup$ – noDispName Jul 10 '13 at 7:46
  • 1
    $\begingroup$ @KutluhanMetin: How would it find the worst case? How would it make a statement about behaviour for $n \to \infty$? $\endgroup$ – Raphael Jul 10 '13 at 8:02
1
$\begingroup$

What you are proposing can be used to implement an algorithm to solve this problem:

Given a runtime bound $\Theta(f)$ and a procedure proc, decide whether proc runs in that time (in the worst case).

There may be special cases where you can decide such things (e.g. certain primitive recursive programs that can be identified as such), but in general, no, you can't decide runtime of programs.

As a matter of fact, you can't even decide between two given runtime bounds.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.