. In the select algorithm that finds the median we divide the input elements into groups of 5. Will the algorithm work in linear time if we divide it into groups of 7? How about 3? Explain your answer--- the asymptotic run time in either case.

we have that it grows more quickly than linear.

Explanation:

It will still work if they are divided into groups of 77, because we will still know that the median of medians is less than at least 44 elements from half of the \lceil n / 7 \rceil⌈n/7⌉ groups, so, it is greater than roughly 4n / 144n/14 of the elements.

Similarly, it is less than roughly 4n / 144n/14 of the elements. So, we are never calling it recursively on more than 10n / 1410n/14 elements. T(n) \le T(n / 7) + T(10n / 14) + O(n)T(n)≤T(n/7)+T(10n/14)+O(n). So, we can show by substitution this is linear.

We guess T(n) < cnT(n)<cn for n < kn<k. Then, for m \ge km≥k,

\begin{aligned} T(m) & \le T(m / 7) + T(10m / 14) + O(m) \\ & \le cm(1 / 7 + 10 / 14) + O(m), \end{aligned}

T(m)

​

≤T(m/7)+T(10m/14)+O(m)

≤cm(1/7+10/14)+O(m),

​

therefore, as long as we have that the constant hidden in the big-Oh notation is less than c / 7c/7, we have the desired result.

Suppose now that we use groups of size 33 instead. So, For similar reasons, we have that the recurrence we are able to get is T(n) = T(\lceil n / 3 \rceil) + T(4n / 6) + O(n) \ge T(n / 3) + T(2n / 3) + O(n)T(n)=T(⌈n/3⌉)+T(4n/6)+O(n)≥T(n/3)+T(2n/3)+O(n) So, we will show it is \ge cn \lg n≥cnlgn.

\begin{aligned} T(m) & \ge c(m / 3)\lg (m / 3) + c(2m / 3) \lg (2m / 3) + O(m) \\ & \ge cm\lg m + O(m), \end{aligned}

T(m)

​

≥c(m/3)lg(m/3)+c(2m/3)lg(2m/3)+O(m)

≥cmlgm+O(m),

​

therefore, we have that it grows more quickly than linear.