How to obtain expected execution time and worst case for algorithms with infinite loop?

Question

I have a one doubt about expected execution time and worst case executio time of algorithms, I was think a simple algorithm but this contain a loop infinite and I don't know about to explain that expected execution time?. I could always determine the time to algorithms with stop conditions.

This is my example (I just know, that more than n/2 can give true):

while (true)
{
  int i = random(0,n-1);
  bool e = decision(i); //Θ(n)
  if (e==true)
     return i;
}

Answer 1

The expected execution time is O(n).

With probability p >= 1/2, the first i will give decision(i) == true, so the loop will terminate after one call to decision.

Let q = 1 - p be the probability that it did not happen. Then, with probability q * p, the second i will give decision(i) == true, so the loop will terminate after two calls to decision.

Similarly, with probability q^2 * p, the third i will give decision(i) == true, so the loop will terminate after three calls to decision, and so on.

By taking the sum, we have the expected number of calls to decision as 1 + q + q^2 + q^3 + .... As q <= 1/2, the sum is at most 1 + 1/2 + 1/4 + 1/8 + ... which has an upper limit of 2. So, the expected number of calls is limited by 2.

In total, as each call to decision takes O(n) time, the expected time to run is O(2*n) which is still O(n) since 2 is a constant.