0
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ 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) $\endgroup$
    – nir shahar
    Mar 4 at 10:17

2 Answers 2

2
$\begingroup$

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.

More interesting is the case without inputs. If you want an input-less, terminating program with unbounded executions then you require a source of (countably) infinite randomness. Without that source, the program's executions form a finitely branching tree. By König's lemma that tree cannot have infinitely many nodes without also having an infinite path. The latter would be a non-terminating execution.

$\endgroup$
0
$\begingroup$

Sure. Consider the following algorithm: flip a fair coin; if it is heads, terminate; if it is tails, go back to the beginning and repeat. There is no upper limit to the amount of time this algorithm could take.

$\endgroup$
1
  • $\begingroup$ This terminates only with probability 1 but it does have a nonterminating execution. $\endgroup$
    – Kai
    Mar 5 at 2:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.