# How to show that this variation of the algorithm (that runs until it finds a solution) still has linear expected running time?

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

1. Pick a (multi-)set $R$ of $\lceil n^\frac{3}{4} \rceil$ elements in $S$ chosen independently and uniformly at random with replacement.

2. Sort the set $R$.

3. Let $d$ be the $(\lfloor \frac{1}{2} n^\frac{3}{4} - \sqrt{n} \rfloor)$-th smallest element in sorted set $R$.

4. Let $d$ be the $(\lceil \frac{1}{2} n^\frac{3}{4} + \sqrt{n} \rceil)$-th smallest element in sorted set $R$.

5. 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\}|$$

6. If $\ell_d > \frac{n}{2}$ or $\ell_u > \frac{n}{2}$ then $FAIL$.

7. If $|C| \leq 4n^\frac{3}{4}$ then sort the set $C$, otherwise $FAIL$.

8. Output the $(\lfloor \frac{n}{2} \rfloor - \ell_d + 1)$th element in the sorted order of $C$.

• What's the algorithm? – usul Sep 19 '16 at 17:27
• Some of us don't have access to the book, and so cannot understand the question. Please make the question self-contained. – Yuval Filmus Sep 19 '16 at 19:12
• Please define what you mean by "linear running time" in the last sentence of your quesiton. Do you mean the expected running time is linear, or that the worst-case running time is linear? Do you know about Las Vegas algorithms? about the difference between BPP vs ZPP? What approaches have you considered, and why did you reject them? Have you read en.wikipedia.org/wiki/Monte_Carlo_algorithm? Please edit the question to clarify. – D.W. Sep 19 '16 at 21:53
• @YuvalFilmus, I transcribed the algorithm in an edit, source can be found here page 53 of the text. The analysis section is well written. I'll attempt an answer. – ryan May 14 '17 at 4:40

I'm assuming you're referring to this as your source.

Short answer: The algorithm terminates in linear time. This does not mean it identifies a median in linear time.

The text first proves, by Theorem 3.9 on page 54, that the algorithm terminates in linear time.

Then it proves, by Theorem 3.13 on page 57, that the probability of failure is bounded by $n^{-1/4}$.

Then the text mentions (page 57):

By repeating Algorithm 3.1 until it succeeds in finding the median, we can obtain an iterative algorithm that never fails but has a random running time. The samples taken in successive runs of the algorithm are independent, so the success of each run is independent of other runs, and hence the number of runs until success is achieved is a geometric random variable. As an exercise, you may wish to show that this variation of the algorithm (that runs until it finds a solution) still has linear expected running time.

The algorithm merely terminates in linear time, making it a Monte Carlo Algorithm. Although by successive runs and a bound on the probability of failure, we can guarantee a success at some point, making it a Las Vegas Algorithm. This successive trial algorithm is what you would attempt to show has an expected linear running time, by working on the geometric random variable represented by $k$ successive trials with bounded failure probability $n^{-1/4}$.