Data Structures, Algorithms, & Applications in C++
Chapter 18, Exercise 33

(a)

The steps in the proof are:

1. The number of groups (and hence medians) is floor(n/9)
2. At least ceil(floor(n/9)/2) of these floor(n/9) medians are less than or equal to the pivot element.
3. In each group, at least 5 elements are less than or equal to the group median.
4. Therefore, at least 5 * ceil(floor(n/9)/2) >= 2.5 * floor(n/9) elements are less than or equal to the pivot.
5. Therefore, at most n - 2.5 * floor(n/9) elements are greater than the pivot.
6. From the way the partitioning code works, we see that the right segment has maximum size when the number of elements that are greater than the pivot is maximum and the remaining elements are equal to the pivot. At most half of these remaining elements can end up in the right segment because each element in the right segment that is equal to the pivot got into the right segment as a result of a swap with an element that is equal to or smaller than the pivot. The swapped element must be in the left segment when done.
7. Therefore, the size of the right segment is at most n - 2.5 * floor(n/9) + 1.25 * floor(n/9)
= n - 1.25 * floor(n/9)
< n - 1.25 (n/9 - 1)
= 31n/36 + 1.25
<= 63n/72 for n >= 90

(b)

The steps in the proof are:

1. The number of groups (and hence medians) is floor(n/5)
2. At least ceil(floor(n/5)/2) of these floor(n/5) medians are less than or equal to the pivot element.
3. In each group, at least 3 elements are less than or equal to the group median.
4. Therefore, at least 3 * ceil(floor(n/5)/2) >= 1.5 * floor(n/9) elements are less than or equal to the pivot.
5. Therefore, at most n - 1.5 * floor(n/5) elements are greater than the pivot.
6. Since all elements are distinct, the size of the right segment is at most n - 1.5 * floor(n/5)
<= n - 1.5 (n/5 - 4/5)
= 0.7n + 1.2
<= 3n/4 for n >= 24