# Randomized Selection

The randomized selection algorithm is the following:

Input: An array $A$ of $n$ (distinct, for simplicity) numbers and a number $k\in [n]$

Output: The the "rank $k$ element" of $A$ (i.e., the one in position $k$ if $A$ was sorted)

Method:

• If there is one element in $A$, return it
• Select an element $p$ (the "pivot") uniformly at random
• Compute the sets $L = \{a\in A : a < p\}$ and $R = \{a\in A : a > p\}$
• If $|L| \ge k$, return the rank $k$ element of $L$.
• Otherwise, return the rank $k - |L|$ element of $R$

I was asked the following question:

Suppose that $k=n/2$, so you are looking for the median, and let $\alpha\in (1/2,1)$ be a constant. What is the probability that, at the first recursive call, the set containing the median has size at most $\alpha n$?

I was told that the answer is $2\alpha - 1$, with the justification "The pivot selected should lie between $1−\alpha$ and $\alpha$ times the original array"

Why? As $\alpha \in (0.5, 1)$, whatever element is chosen as pivot is either larger or smaller than more than half the original elements. The median always lies in the larger subarray, because the elements in the partitioned subarray are always less than the pivot.

If the pivot lies in the first half of the original array (less than half of them), the median will surely be in the second larger half, because once the median is found, it must be in the middle position of the array, and everything before the pivot is smaller as stated above.

If the pivot lies in the second half of the original array (more than half of the elements), the median will surely first larger half, for the same reason, everything before the pivot is considered smaller.

Example:

3 4 5 8 7 9 2 1 6 10

The median is 5.

Supposed the chosen pivot is 2. So after the first iteration, it becomes:

1 2 ....bigger part....

Only 1 and 2 are swapped after the first iteration. Number 5 (the median) is still in the first greater half (accroding to the pivot 2). The point is, median always lies on greater half, how can it have a chance to stay in a smaller subarray?

• We did not sit in your lecture, so please explain the method. – Raphael Apr 18 '12 at 18:47
• Without knowing which precises algorithm you are talking about, your question is not readable. You seem to use $.5$ in multiple capacities; I tried to edit but am not sure I caught the meaning. Please revise so the question is clear. Voting to close until then. – Raphael Apr 18 '12 at 18:56
• It's Selection Algorithm using Randomized Method, as opposed to Deterministic Method. – Amumu Apr 18 '12 at 19:35
• There are many ways to select an element randomly. – Raphael Apr 18 '12 at 19:52
• @Amumu: I edited it to describe the algorithm. In a forum like this, not everybody will know what you are talking about, and there is a very different randomized approach to selection that is easier to analyze. – Louis Apr 18 '12 at 19:52

Suppose your array has $n$ elements. As you have noted, the median is always in the bigger part after the first partition. The bigger part has size at most $\alpha n$ if the smaller part has size at least $(1-\alpha) n$. This happens when you pick a pivot that isn't one of the smallest or largest $(1-\alpha) n$ elements. Because $\alpha > 1/2$, you know these are disjoint sets, so the probability of hitting one of the bad pivots is just $2 - 2\alpha$, and $1- 2 + 2\alpha=2\alpha - 1$.
• Because it makes $1-\alpha < 1/2$, so $(1-\alpha)n < n - (1-\alpha)n$. – Louis Apr 18 '12 at 19:33
• Here, I am saying that a pivot is "bad" if it makes the bigger part larger than you want, which is $\alpha n$ size. What you call bad corresponds to $\alpha = 3/4$. I suspect the point of the question is that your instructor wanted you to see that the $O(\cdot)$ order of the expected running time is not changed by changing $\alpha$. – Louis Apr 18 '12 at 19:50