# Can a program that terminates have a running time of infinity? (Or not have an upper bound)

Can we have an algorithm that takes some input and does something random to it (in such a way that the algorithm does terminate) which does not have a worst-case running time upper-bound?

A (non-)example which shows what I mean: If let's say that my algorithm is one that takes an input number, generates a random number, adds them both and puts the program to sleep for that number of seconds. Would the running time here be unbounded (even though the algorithm would terminate)? I can see how in this example, it might not be, because we can represent the running time in terms of both the input size and the randomly generated number.

But could there be some other (possibly non-deterministic) algorithm with such traits? That does something random to the input, terminates and does not have an upper bound for worst-case running time?

Thank you!

• Well, it has to use randomness to do that... But it still is possible to express the run-time with a function over the randomness. So my educated guess is "no" (not formally proven though) Mar 4 at 10:17

Since you allow inputs, you can imagine a program that inputs a natural number $$n$$ and then performs $$n$$ steps. No further randomness is required.