What's the worst case running time?
while flip_coin() == heads: continue;
In other words, I flip a fair coin until I get tails. Of course we knows the expected number of flips is 2. But the worst case is what?
I have usually said "infinity" in lecture. But that event (that the program never terminates) has probability zero, so is it correct?
On the other hand, if I give any finite worst-case number of flips, there is a non-zero probability that the program could require more time.
So it seems like a paradox of sorts, yes?
I think you have here a case of maximum vs. supremum.
There is indeed a zero probability for the program to take infinitely long to terminate. The set of times the program has a nonzero probability of terminating in does not include infinity, but it is unbounded. So if you define the "worst case running time" as the maximum of this set, it does not exist. On the other hand, if you define it as the supremum of this set, it exists as infinity.