Running time of algorithms that sometimes loop forever

Question

Consider the following algorithm that computes the sum of two integers (toy example):

INPUT: Integers (a,b)

 1. Toss a coin c
 2. If c = 0, then loop forever
 3. If c = 1, then compute and output a+b

What is the running time of this algorithm? The "strict" running time (defined as a strict upper bound on the running time over all inputs and all possible random choices of the algorithm) is infinite. The "expected" running time (defined as the average running time over all inputs and random choices) is infinite, too.

Thus, apparently this is an algorithm whose running time (strict/expected) is infinite. However, the algorithm still appears to be useful, since it produces a reasonable result with probability 1/2.

Is there a notion of "running time" in computer science that captures such algorithms? Can you point me to references or a textbook?

Thanks!

Answer 1

The textbook Computational Complexity: A Modern Approach by Arora and Barak looks at the class $ZTIME(T(n))$ (chapter 7), of algorithms whose expected running time is bounded by $T(n)$ (but which do not necessarily halt on all random seeds). This class cannot capture the notion you describe, because you are looking for a function whose range includes $\infty$, whereas Arora and Barak only look at time functions $T\colon \mathbb{N}\to \mathbb{N}$. Another close analogue to what you describe is $RE$, the class of problems recognizable by a Turing Machine which is only guaranteed to halt on yes-instances.

To my knowledge, even the Complexity Zoo doesn't cover algorithms with infinite expected running time. The reason, I suppose, that these algorithms aren't studied is twofold: (1) they are not useful, because an algorithm with an infinite running time produces no answer and (2) they are not needed to solve any problems that cannot be solved by a deterministic computer with a finite or unbounded running time. To see (2), imagine an algorithm $A$ for deciding membership in a language, in the sense that when it halts, it outputs the right answer, but it is not guaranteed to halt for all inputs. Then you can just do a breadth-first search on the configuration graph. The class of problems solvable with these restrictions is $RE$. If the algorithm is guaranteed to have at least one halting path, the class is $R$.

Answer 2

I doubt this idea has been studied because, to me, it doesn't seem at all useful. The only thing that would allow you to use your example algorithm is the fact that you have an exact running time bound on the terminating option, which means that you can detect that you were in the non-halting case, abort and restart. In general, of course, you can't detect that you're in a non-halting case, so you can't use this trick. Also, the trick relies on the algorithm being probabilistic. In a deterministic algorithm, even if you could detect the infinite loop, you'd only be able to return "I don't know", which isn't a correct answer to whatever problem you're trying to solve.

The closest concept I'm aware of is Las Vegas algorithms. These are randomized algorithms that always produce the correct answer on termination, and that terminate in expected finite time. Indeed, the abort-and-restart version of your example algorithm is an example of a Las Vegas algorithm – in expectation, you need one abort (assuming the coin is unbiased).