0
$\begingroup$

How to get the expected time complexity of while loop below?

While infinity:
  case1: Return 0 with a probability of p(1 - p)
  case2: Return 1 with a probability of p(1 - p)
  case3: otherwise repeat this loop until return 0 or 1

I can understand the probability that this loop runs only one time is $2p(1 - p)$. But I cannot understand how much the expected run time of this is. Can anyone let me know it and why?

$\endgroup$
1
  • 2
    $\begingroup$ Are you familiar with geometric random variables? $\endgroup$ May 29, 2021 at 11:01

2 Answers 2

1
$\begingroup$

You should calculate the probability that the while loop runs exactly $k$ times, for $k\in\mathbb{N}$.

Then the expected number of loops is $\sum\limits_{k=0}^{\infty}k\times\mathbb{P}(\text{loop runs }k\text{ times})$.

$\endgroup$
1
$\begingroup$

Define $q:=2p(1-p)$ the probability that the while loop halts at a certain point.

The probability the loop runs exactly once is $q$
The probability the loop runs exactly twice is $(1-q)\cdot q$
The probability the loop runs exactly three times is $(1-q)^2 \cdot q$

And you can see where this is going: the probability the loop runs exactly $n$ times is given by: $(1-q)^{n-1}\cdot q$ and as @Yuval Filmus suggested, this is a geometric distribution.

According to wikipedia, the expected value of such a geometric distribution is $\frac{1}{q}$, so the average complexity of your loop is: $\frac{1}{2 p (1-p)}$

$\endgroup$

Your Answer

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

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