Return to Question

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

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

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?

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

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?

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?