rightwayman's blog: [Algo] Exercise 9.3

rightwayman's blog: [Algo] Exercise 9.3

Exercise 9.3-1
In the algorithm SELECT, the input elements are divided into groups of 5. Will the algorithm work in linear time if they are divided into groups of 7? Argue that SELECT does not run in linear time if groups of 3 are used.
solution:
(1) groups of 7 are used
# of elements greater than the median of median is at least
.
The recurrence can be rewritten as
.
The process of proving is similar to the textbook, and we will prove that finally.

(2) groups of 3 are used
# of elements greater than the median of median is at least
.
The recurrence can be rewritten as
.
Before we derive the following steps, we can glance at the equation and find out the right hand side . Suppose that for some positive constant c.  By substitution, we have

Since , we cannot derive that . Hence, SELECT does not run in linear time if groups of 3 are used.

Read full article from rightwayman's blog: [Algo] Exercise 9.3