2
$\begingroup$

Short version: I want to know where the $-2$ comes from in the formula on p. 221 of CLRS 3rd edition.

Long version: CLRS (3rd ed.) give an algorithm for $O(n)$ worst case arbitrary order statistic of $n$ distinct numbers. The algorithm is roughly:

Input: an array of $n$ elements and $i$, the number of the order statistic to return from the elements.

  1. Divide the $n$ elements into $\lfloor n/5 \rfloor$ groups of 5 elements each along with an optional group containing $n\mod{5}$ elements (resulting in $\lceil n/5 \rceil$ groups.)
  2. Find the median of each of the groups by sorting.
  3. Recurse, using the $\lceil n/5 \rceil$ medians as the array and $\lfloor\lceil n/5 \rceil/2\rfloor$ as the order statistic, resulting in the median-of-medians.
  4. Partition the $n$ elements around the median-of-medians (using a quicksort-like $O(n)$ partitioning algorithm.
  5. Letting $k-1$ be the number of elements less than the median-of-medians, if $i = k$, return the median-of-medians. Otherwise recurse: if $i < k$ then recurse finding the $i$th order statistic of the $k-1$ elements less than the median-of-medians; if $i > k$, then recurse finding the $i-k$th order statistic of the $n-k$ elements greater than the median-of-medians.

Output: the $i$th order statistic of the $n$ numbers.

In the proof of the runtime, CLRS argue that the number of elements greater than the median-of-medians is at least:

$$ 3 \bigg(\bigg\lceil \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil - 2\bigg) $$

The reasoning is that half of the medians are greater than the median-of-medians, and each of those medians' groups has at least three elements greater than the median-of-medians (the median itself plus the two elements greater than the median.) That would result in

$$ 3 \bigg(\bigg\lceil \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil\bigg) $$

for the lower bound on the number of elements greater than the median-of-medians.

But we must account for two things: the group containing the median-of-medians (the median-of-medians is not greater than itself) and the group that contains the modulo leftovers. To account for the group containing the median-of-medians, we subtract 1, resulting in:

$$ 3 \bigg(\bigg\lceil \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil\bigg) - 1 $$

and I think that for the modulo leftovers group, we should subtract 4, because the least number of elements in the group is 1. So that would give:

$$ 3 \bigg(\bigg\lceil \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil\bigg) - 5 $$

which can be transformed into

$$ 3 \bigg(\bigg\lceil \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil - 2\bigg) + 1 $$

Why does my analysis lead to a lower-bound 1 greater than that given in CLRS?

$\endgroup$
2
$\begingroup$

In

$$ 3 \bigg(\bigg\lceil \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil - 2\bigg) $$

we are subtracting 2 in order to discard the group containing the median of medians and the group of leftovers. So, 2 is the number of groups we are discarding.

First of all, note that there may not be a group of leftover elements: if $n$ is an exact multiple of 5 there will be no leftover group. We are interested in bounding from below the number of elements greater than the median-of-medians in the worst case, so suppose that a leftover group exists. Therefore, it will contain at least an element and no more than 4 elements. If you want to reason in terms of elements to be discarded and not in terms of groups, then we must discard exactly 3 elements for the group containing the median of medians (including the median of the medians), and at most 2 element from the leftovers group (if this group contains 1 or 2 elements you do not discard any element; if this group contains 3 or 4 elements, then you discard respectively 1 or 2 elements which are greater than the group's median). So, you discard in the worst case (leftover group with 4 elements) 3 + 2 elements:

$$ 3 \bigg(\bigg\lceil \frac{1}2 \bigg\lceil{\frac{n}5} \bigg\rceil \bigg\rceil\bigg) - 5 $$

$\endgroup$
  • $\begingroup$ "2 is the number of groups we are discarding" okay yes I understand that now. $\endgroup$ – Carl G Jan 7 '14 at 21:42
  • $\begingroup$ I'm not sure that your analysis of the elements is completely correct, though. The quantity $3(\ldots)$ is three elements per group: 1 median plus 2 elements greater than the median. One of these groups contains the median-of-medians, and so you would subtract 1 to remove the median-of-medians, not 3, from it. If you subtract 3, you also remove the two elements in the median-of-medians' group that are actually greater than the median-of-medians. I agree that at most we remove 2 elements from leftovers. So if I am correct, now it is $-1$ inside the parentheses. Thanks! $\endgroup$ – Carl G Jan 7 '14 at 22:08
  • $\begingroup$ Remember that, by assumption, all of the elements are distinct. That means that in the group of the median of medians, only two elements are greater than the median of medians since the median of median can not be greater than itself! Therefore, you must remove 3 elements, including the median of medians, that are less than the median of medians from that group, not one. $\endgroup$ – Massimo Cafaro Jan 8 '14 at 8:55
  • $\begingroup$ Right, but the two elements less than the median-of-medians are not accounted for in the first place. (The two elements less than any median are not accounted in any group.) The $3$ at the beginning is '3 elements per group (groups that will have elements greater than the median-of-medians), i.e. the median of that group and the two elements greater than the median of that group.' $\endgroup$ – Carl G Jan 8 '14 at 17:26
  • $\begingroup$ Sure, but I said that you must subtract -3 to the expression just $after$ the parenthesis, so that you are subtracting 3 elements which are $less$ than the median of medians for that group and this is correct because you are computing the number of elements that are greater than the median of medians. You also subtract additional 2 elements related to the leftovers group for a total of 5. $\endgroup$ – Massimo Cafaro Jan 8 '14 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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