Recall that MERGE SORT splits the input array into two halves of almost equal sizes, and after each half is sorted recursively, both of them are merged into a sorted array. Let's now consider a variant of MERGE SORT, where instead of splitting the array into two equal size parts, we split it into four parts of almost equal sizes, recursively sort out each part, and at the end, merge all four parts together into a sorted final array. In what follows, we want to find the time complexity of this variant of MERGE_SORT. (a) Define T(n) as the worst-case running time of this variant on any input of size n. Find a recursive formula for T(n), i.e. write T(n) in terms of T(k) for some 1 < k < n. (b) Draw the corresponding recursion tree and find the explicit answer for T(n). (c) Prove your result in part (b) formally using strong induction. For full credit, your answer must use (.) notation, i.e., you should obtain both an upper bound and a lower bound.