# Randomized Algorithm Log-Space Exp-Time

I'm looking for an example of a randomized algorithm that halts with probability 1 (halts almost surely), uses only logarithmic space (worst case) and whose expected run time is not polynomial in the size of the input.

• Can you edit your question to define "always halts" more precisely, please? If the probability of not halting is 0, does that qualify as "always halts"? Do you mean for all inputs, the probability that it halts is 1? Or do you mean that for all inputs and all possible coins (choices of random values), it halts?
– D.W.
Dec 29, 2021 at 6:40
• Please don't use "EDIT:". Rather than appending more information at the end, please revise your question so that it reads well for someone who encounters it for the first time. We're hoping to build up an archive of high-quality questions that will be useful to others in the future. See cs.meta.stackexchange.com/q/657/755 for more details.
– D.W.
Dec 29, 2021 at 22:22
• Can you now clarify what you mean by "run time"? Do you mean "expected running time" (expectation taken over the random choices made by the algorithm, for the worst-case input)? Do you mean worst-case running time (both the worst-case input, and the worst-case set of random choices)? Something else? It affects the answer.
– D.W.
Dec 29, 2021 at 22:24
• In essence, halts almost surely, worst case logarithmic space, worst case exponential time Jan 2, 2022 at 18:31
• This still doesn't answer what you mean by "worst case". Does that mean worst over all possible random choices that happen during execution of the algorithm, as well as all possible inputs? If you'd like an answer, I recommend that you edit your question to specify this very explicitly and clearly in the question. Don't force us to guess -- as then if we answer based on some guess at what you're asking, and it wasn't the assumption you were hoping for, then both you and we have wasted our time.
– D.W.
Jan 3, 2022 at 2:29