1. **Problem statement:** We have a variant of the Median-of-Five algorithm using $n/3$ blocks of size 3 instead of $n/5$ blocks of size 5. Our goals are: - a) Derive a recursive time complexity formula $T(n)$ for this algorithm. - b) Check if $T(n) \in O(n)$ by guessing and verifying. 2. **Deriving the recurrence (part a):** - Divide input of size $n$ into $n/3$ groups of 3 elements each. - Find median of each group: for each group of size 3, median costs constant time $O(1)$. - Next, recursively find the median of these $n/3$ medians. Let this take $T(n/3)$ time. - Use this median of medians as pivot to partition the array in $O(n)$. - The partition splits input into subproblems. The lower bound on the size of the larger partition is analyzed similarly to Median-of-Five. 3. **Size of recursive calls:** - The number of medians is $n/3$. - Median of medians recursion cost: $T(n/3)$. - Partitioning the array around pivot: $O(n)$. 4. **Lower bound on partition size:** - Each median is the median of 3 elements. - Half of these medians are greater than or equal to the median-of-medians. - Each such median is greater than at least 2 elements in its group. - So the number of elements greater than or equal to pivot is at least $2 \times \lceil \frac{n}{6} \rceil = \frac{n}{3}$ (approximately). - Thus, the largest partition has size at most $n - \frac{n}{3} = \frac{2n}{3}$. 5. **Recursive formula:** $$ T(n) \leq T\left(\frac{n}{3}\right) + T\left(\frac{2n}{3}\right) + cn $$ Here $cn$ corresponds to the linear partition and median finding in groups. 6. **Guess $T(n) \leq dn$ for some constant $d$ (part b):** Substitute into the recurrence: $$ T(n) \leq d\frac{n}{3} + d\frac{2n}{3} + cn = dn + cn $$ which simplifies to: $$ T(n) \leq n(d + c) $$ This means $T(n) \in O(n)$ only if $d + c \leq d$ which is impossible because $c > 0$. 7. **Conclusion:** The recurrence $$ T(n) \leq T\left(\frac{n}{3}\right) + T\left(\frac{2n}{3}\right) + cn $$ cannot be solved in $O(n)$ time. **Therefore, $T(n)$ is not linear and grows faster than $O(n)$.