Problem $3.$ Suppose that we modify PARtition so that it chooses the median element as the pivot in calls that occur in nodes of the recursion tree of a call to QUICKSORT whose depth in the recursion tree is divisible by $3,$ and it chooses the maximum element as the pivot in calls that occur in nodes all other depth of this recursion tree.

Assume that the running time of this modified PARtition is still $(n)$ on any subarray of length $n.$ You may assume that the root of a recursion tree starts at level $0($which is divisible by $3),$ its children are at level $1,$ etc. For example, the modified PARTITION chooses the median element at the root of the recursion tree, in the next two layers of the recursion tree it chooses the max, and in level $3$ of the recursion tree it chooses the median again, and so on$.$

Your job is to write down a recurrence relation for the running time of this version of QUICKSORT given an array $n$ distinct elements and solve it asymptotically, i$.$e$.,$ give your answer as $(f(n))$ for some function $f(n)$ using either the Unrolling Method or the Recursion$-$Tree Method. Show your work.

Answer.