We have studied the linear time selection algorithm applied on n elements. Assume that all n elements are different. In the algorithm we have studied, we used group size of 5. We proved that the number of elements that are guaranteed to be larger than the median of medians is lower bounded by G(n, 5) = 3n/10 - 6. Similarly, the number of elements that are guaranteed to be smaller than the median of medians is also lower bounded by G(n, 5). Therefore, the number of elements on either side of the median of medians after the partition is upper bounded by U(n, 5) = n - G(n, 5) = 7n/10 6. We concluded that the time complexity T(n) of the algorithm satisfy the relation T(n) <= T(n/5) T(7n/10 6) Theta(n). This leads to T(n) = Theta(n). Suppose that we use group size 7 (instead of 5), what is the recurrence relation for T(n)



Answer :

Other Questions