# Exercise 9.3.1

In 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.

### Groups of 7

The algorithm will work if the elements are divided in groups of 7. On each partitioning, the minimum number of elements that are less than (or greater than) $x$ will be:

$$ 4 \bigg(\bigg\lceil \frac{1}{2} \Big\lceil \frac{n}{7} \Big\rceil \bigg\rceil - 2 \bigg) \ge \frac{2n}{7} - 8 $$

The partitioning will reduce the subproblem to size at most $5n/7 + 8$. This yields the following recurrence:

$$ T(n) = \begin{cases} \O(1) & \text{ if } n < n_0 \\ T(\lceil n/7 \rceil) + T(5n/7 + 8) + \O(n) & \text{ if } n \ge n_0 \end{cases} $$

We guess $T(n) \le cn$ and bound the non-recursive term with $an$:

$$ \begin{aligned} T(n) & \le c\lceil n/7 \rceil + c(5n/7 + 8) + an \\ & \le cn/7 + c + 5cn/7 + 8c + an \\ & = 6cn/7 + 9c + an \\ & = cn + (-cn/7 + 9c + an) \\ & \le cn \\ & = \O(n) \end{aligned} $$

The last step holds when $(-cn/7 + 9c + an) \le 0$. That is:

$$ -cn/7 + 9c + an \le 0 \\ \Downarrow \\ c(n/7 - 9) \ge an \\ \Downarrow \\ \frac{c(n - 63)}{7} \ge an \\ \Downarrow \\ c \ge \frac{7an}{n - 63} $$

By picking $n_0 = 126$ and $n \le n_0$, we get that $n/(n - 63) \le 2$. Then we just need $c \ge 14a$.

### Groups of 3

The algorithm will not work for groups of three. The number of elements that are less than (or greater than) the median-of-medians is:

$$ 2 \bigg(\bigg\lceil \frac{1}{2} \Big\lceil \frac{n}{3} \Big\rceil \bigg\rceil - 2 \bigg) \ge \frac{n}{3} - 4 $$

The recurrence is thus:

$$ T(n) = T(\lceil n/3 \rceil) + T(2n/3 + 4) + \O(n) $$

We're going to prove that $T(n) = \omega(n)$ using the substitution method. We guess that $T(n) > cn$ and bound the non-recursive term with $an$.

$$ \begin{aligned} T(n) & > c\lceil n/3 \rceil + c(2n/3 + 2) + an \\ & > cn/3 + c + 2cn/3 + 2c + an \\ & = cn + 3c + an & (c > 0, a > 0, n > 0)\\ & > cn \\ & = \omega(n) \end{aligned} $$

The calculation above holds for any $c > 0$.