patternMinor
Is there an algorithm which can compute every algorithm's time complexity?
Viewed 0 times
cancomputeeverytimealgorithmwhichtherecomplexity
Problem
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#13196, answer score: 3
Revisions (0)
No revisions yet.