rightwayman's blog: [Algo] Exercise 9.3
Exercise 9.3-1In 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
No comments:
Post a Comment