Let $p$ be the probability that process $B$ gives a cut of value at least $|E|/2.$ Then by [[Expectation of Geometric Distribution]], the expected number of steps until the algorithm terminates is $1/p.$ Let $m:=|E|.$ Let $Y(\text{cut})=\text{value of cut}.$ Then we have $\mathbb{E}[Y]=m/2.$ Moreover, $\begin{align} \mathbb{E}[Y]&=\sum_{i<m/2}i\cdot\mathbb{P}(Y=i)+\sum_{m/2\leq i\leq m}i\cdot\mathbb{P}(Y=i) \\ &\leq \sum_{i<m/2}\left( \frac{m}{2}-1 \right)\mathbb{P}(Y=i)+\sum_{m/2\leq i\leq m}m\cdot \mathbb{P}(Y=i) \end{align}$Now $p=\sum_{m/2\leq i\leq m}\mathbb{P}(Y=i)$ and $1-p=\sum_{i<m/2}\mathbb{P}(Y=i)$ thus $\mathbb{E}[Y]\leq\left( \frac{m}{2} -1\right)(1-p)+mp$and finally we conclude that $\frac{1}{p}\leq(m+2)/m.$ # References - [[Week 9 Max Cut.pdf]].