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

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?

• Are you familiar with geometric random variables? May 29, 2021 at 11:01

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})$$.

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)}$$