Ravindra Ranwala's Blog

Exercise 9.3-1 asks you to show that the $SELECT$ algorithm still runs in linear time if the elements are divided into groups of 7. This problem asks about dividing into groups of 3. Show that $SELECT$ runs in linear time if you divide the elements into groups whose size is any odd constant greater than 3. Show that $SELECT$ runs in $O(n\; lg\; n)$ time if you divide the elements into groups of size 3 Because the bound in part (b) is just an upper bound, we do not know whether the groups-of-3 strategy actually runs in $O(n)$ time. But by repeating the groups-of-3 idea on the middle groups of medians, we can pick a pivot that guarantees $O(n)$ time. The $SELECT3$ algorithm on the next page determines the $i^{\;th}$ smallest of an input array of $n \gt 1$ distinct elements. Describe in English how the $SELECT3$ algorithm works.Include in your description one or more suitable diagrams. Show that $SELECT3$ runs in $O(n)$ time in the worst case. [1]   The worst-case linear-time median-f...