In the last section of chapter 3 (page 57) in Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal, a randomized algorithm is discussed for finding the median of a set $S$ of distinct elements in $O(n)$ time. The algorithm discussed is a Monte Carlo algorithm. As such if we would like to run this variation of algorithm till we find a solution, how do we show that it still has a linear running time?The Algorithm (source, starts on slide 66, page 53):Input: A set $S$ of $n$ elements over a totally ordered  universe$^{***}$.Output: The median of set $S$, denoted by $m$.Pick a (multi-)set $R$ of $\lceil n^\frac{3}{4} \rceil$ elements in $S$ chosen independently and uniformly at random with  replacement.Sort the set $R$.Let $d$ be the $(\lfloor \frac{1}{2} n^\frac{3}{4} - \sqrt{n} \rfloor)$-th  smallest element in sorted set $R$.Let $d$ be the $(\lceil \frac{1}{2} n^\frac{3}{4} + \sqrt{n} \rceil)$-th  smallest element in sorted set $R$.By comparing every element in $S$ to $d$ and $u$, compute the set: $$C = \left\{ x \in S : d \leq x \leq u \right\}$$ and the numbers  $$\ell_d = |\{x \in S : x  < d\}|$$ and the numbers $$\ell_u = |\{x \in S : x > u\}|$$If $\ell_d > \frac{n}{2}$ or $\ell_u > \frac{n}{2}$ then $FAIL$.If $|C| \leq 4n^\frac{3}{4}$ then sort the set $C$, otherwise $FAIL$.Output the $(\lfloor \frac{n}{2} \rfloor - \ell_d + 1)$th element in the sorted order of $C$.
How to show that this variation of the algorithm (that runs until it finds a solution) still has linear expected running time?
algorithms;algorithm analysis;runtime analysis;randomized algorithms