Question

In the algorithm SELECT, the input elements are divided into groups of 5. Show that the algorithm works in linear time if they are divided into groups of 9

Answer 1

Selection Algorithm is an algorithm for finding the kth smallest or largest number in a list or an array.

The algorithm will work in linear time if they are divided into groups of 9.

There are n/9 groups with at least 4.(1/2).(n/9) = (2n/9) elements that are less than or equal to the median of the medians and at least as many that are greater than or equal to the median of medians.

Thus, the larger subset after partitioning has at most n − 2n/9 = 7n/9 elements.

The running time is T(n) = T(n/9) + T(7n/9) + Θ(n)

Using substitution we assume: T(k) ≤ c ∗ k for k < n

= T(k) ≤ c ∗ (n/9) + c ∗ (7n/9) + c1n

= T(k) ≤ c ∗ (8n/9) + c1n

= T(k) ≤ c ∗ n + (c1 − c ∗ (1/9))n

= T(k) ≤ c ∗n which is linear if (c1 − c ∗ (1/9)) ≤ 0

Hence, the algorithm will work in linear time if they are divided into groups of 9.