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!