Problem $4.$ Suppose that we modify Partition so that it chooses the minimum element as the pivot that occur in nodes of the recursion tree whose depth is divisible by $2,$ and it chooses the median 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 $\backslash (\backslash$Theta$($n$)\backslash )$ on any subarray of length $\backslash ($ n $\backslash ).$ And the root of a recursion tree starts at level $0($which is divisible by $2),$ 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 layer of the recursion tree it chooses the minimum element, and so on$.$

Write a recurrence relation for the running time of modified Quicksort given an array $\backslash ($ n $\backslash )$ distinct elements. The final recurrence relation is sufficient, no need to solve it asymptotically.