14
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ We did not sit in your lecture, so please explain the method. $\endgroup$
    – Raphael ♦
    Apr 18, 2012 at 18:47
  • $\begingroup$ 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. $\endgroup$
    – Raphael ♦
    Apr 18, 2012 at 18:56
  • $\begingroup$ It's Selection Algorithm using Randomized Method, as opposed to Deterministic Method. $\endgroup$
    – Amumu
    Apr 18, 2012 at 19:35
  • $\begingroup$ There are many ways to select an element randomly. $\endgroup$
    – Raphael ♦
    Apr 18, 2012 at 19:52
  • 2
    $\begingroup$ @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. $\endgroup$
    – Louis
    Apr 18, 2012 at 19:52

1 Answer 1

Reset to default
12
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for the answer. I still have a few things unclear. So, what does α>1/2 have anything to do with disjoint sets? I thought that when we always have disjoint sets with this method regardless of subarray size. $\endgroup$
    – Amumu
    Apr 18, 2012 at 19:29
  • $\begingroup$ Because it makes $1-\alpha < 1/2$, so $(1-\alpha)n < n - (1-\alpha)n$. $\endgroup$
    – Louis
    Apr 18, 2012 at 19:33
  • $\begingroup$ Just one last thing: What does bad/good pivot have to do with this? As far as I know, good pivot is generally in 25-75 range (which splits original arrays in from 25%-75%), and the bad one is outside that range, and the worse is usually at start or end of the original array. But this? $\endgroup$
    – Amumu
    Apr 18, 2012 at 19:41
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Louis
    Apr 18, 2012 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.