1. **State the problem:** We have a variant of the Median-of-Five algorithm where the input of size $n$ is partitioned into $\frac{n}{3}$ blocks each of size 3. 2. **Part (a): Derive recursive formula for time complexity $T(n)$** - Step 1: Partition the input into $\frac{n}{3}$ groups of size 3. - Step 2: Find median of each group by sorting each group of size 3. Sorting 3 elements takes constant time $O(1)$ per group. - Step 3: Recursively select the median of the medians from the $\frac{n}{3}$ medians. This takes time $T(\frac{n}{3})$. - Step 4: Partition the array around the median of medians. This requires $O(n)$ time. - Step 5: Recursively search on one side of partition, with size at most $cn$ for some constant $c<1$. The key is determining the worst-case split size after partitioning. 3. **Finding the size of the largest partition after partitioning**: - Each median of group of size 3 is greater than exactly one element in its group. - Median of medians $m$ is greater than at least half of the medians, so it is greater than at least half of the $\frac{n}{3}$ groups. - Each such group contributes at least 2 elements less than or equal to $m$ (the median and one smaller). - So, at least $\frac{n}{6}$ groups contribute 2 elements each, total $\frac{n}{3}$ elements less than or equal to $m$. Similarly, at least $\frac{n}{3}$ elements are greater than or equal to $m$. Hence, the worst-case size of partition to recurse on is $$n - \frac{n}{3} = \frac{2n}{3}$$ 4. **Formulating the recurrence:** $$ T(n) \leq T\left(\frac{n}{3}\right) + T\left(\frac{2n}{3}\right) + cn $$ where $cn$ accounts for partitioning and medians computation. 5. **Part (b): Guess if $T(n) \in O(n)$ and test** Assume $T(n) \leq an$ for some constant $a$. Substitute into the recurrence: $$ T(n) \leq a\frac{n}{3} + a\frac{2n}{3} + cn = an + cn = n(a + c) $$ To satisfy $T(n) \leq an$, we need: $$ n(a + c) \leq an \implies a + c \leq a \implies c \leq 0 $$ But $c > 0$ (since partitioning takes positive time), so this is impossible. 6. **Conclusion:** The recurrence does not solve to $O(n)$ with the guessed constants, so $T(n) \in O(n)$ cannot be guaranteed. Hence, the algorithm with block size 3 has worse time complexity than the Median-of-Five which guarantees $O(n)$. **Final answer:** - Recurrence: $$T(n) \leq T\left(\frac{n}{3}\right) + T\left(\frac{2n}{3}\right) + cn$$ - It is impossible to guarantee $T(n) \in O(n)$ from this recurrence.