Is there any algorithm that finds the time complexity of another algorithm provided that it halts?

Question

Let us suppose that we have some algorithm A that halts for all valid inputs, can we prove the existence of another algorithm B that takes A as input and calculates the time complexity of A.

Are there any examples of existing algorithms/programs that do this?

• nir shahar: this is a really interesting problem!

Answer 1

I think this is correct and incorrect at the same time. It depends on how we define the problem we want to solve.

Formulation I

If we are interested in an algorithm that given $\langle M, w\rangle$ will tell you how much time $M$ runs on $w$ (assuming it halts), then there is such an algorithm: emulate $M$ on $w$ and count the number of steps it does until it halts.

---

Formulation II

But, if we are interested in an algorithm that given $\langle M\rangle$ will give you a function $f:\mathbb{N}\rightarrow \mathbb{N}$ that bounds the running time of $M$, things get a little bit more complicated.

First, how do we describe a function $f$ with finite storage? there are $|\mathbb{N}^\mathbb{N}|=2^{\aleph_0}$ functions, and 2ドル^{\aleph_0}$ words in $\{0,1\}^*$ as well. This means there is some way to map each word to a function and vice versa. We will ignore from now the problem of computing this mapping between words and functions, and will still show there is no algorithm for the problem.

Assume towards contradiction there is some $\hat M$ that solves our problem. Let us create a new machine $M'$ that given input $\langle M\rangle $, will first emulate $\hat M$ on $M$ to find some $f$ which describes the upper bound on the time it takes $M$ to halt (assuming it halts). Then, $M'$ will enter a loop for $f(|\langle M'\rangle |) + 1$ steps.

Now, consider what happens when $M'$ runs on the input $\langle M'\rangle$. $\hat M$ will give an upper bound $f$ on the running time of $M'$, and $M'$ will run for more than $f(|\langle M' \rangle|)$ steps, contradicting that $f$ is an upper bound (since the original input of $M'$ was $\langle M'\rangle$).

Thus, no such $\hat M$ can ever exist!

• nir shahar: To summarize what is written above, we can use a proof similar to the halting problem to show that there is no such algorithm

Answer 2

The answer by nir shahar goes to the point.

Another way to see this is to consider Radó's non-computable function $S(n)$ (the maximum number of steps a Turing machine with $n$ states does when started with an empty tape before halting). If you could compute your function $M$, you could compute $S$ (for each TM of $n$ states compute your function $M$, run the TM for $M$ steps, if it hasn't stopped yet, it won't halt; the maximal value found that way is $S(n)$).

The paper is rather simple, and enlightening: Radó, "On Non‐Computable Functions", Bell System Technical Journal 41(3), pp. 877-884 (may 1962), doi https://doi.org/10.1002/j.1538-7305.1962.tb00480.x.