Can you please explain the lower and upper bound conclusions. The given recurrence for the modified merge sort is T(n) = T(n/4) + T(3n/4) + n.

Suppose in MergeSort we split the given array of size n to two subarrays of size n/4 and size 3n/4 respectively, sort them, and merge the results. Use the recurrence tree method to guess a tight upper bound and a tight lower bound, and prove your guesses are tight and correct. Solution: Draw a recursion tree. You will find the shortest path from the root to a leaf where the given array size n is always reduced to n/4 and the longest path where the size n is always reduced to 3n/4. The shortest path will provide us the asymptotic lower bound whereas the longest path will give us the upper bound. Lower Bound : Suppose we have height k in the shortest path. Then, assuming n is a power of 4 , 4kn=1n=4klog4n=k. So, T(n)=(nlogn). Upper Bound: Suppose we have height k in the longest path. Then, (4/3)kn=1n=(4/3)k log(4/3)n=k. So, T(n)=O(nlogn)