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?