Let MergeSort3 be an algorithm that performs Merge Sorting in the traditional sense except for it breaks the array up into three parts instead on two, thus it also performs at n log(n). MergeSort_k is described below, what steps are problematic for the runtime assumptions, and why doesn't it meet this assumption? What is the actual Big-O runtime?

i. Instead of MergeSort3 as above, consider a version MergeSort_k which breaks up the st A recursively into k parts, and uses a routine Mergek similar to the Merge3 you wrote in part ii. The routine Merge.k takes k sorted lists of size n/k, and returns a sorted list of size . Your approach in part (a) still applies: we've already seen that Merge.k runs in time O(n) for k- 2 and k = 3, and it's not hard to see that the natural generalization also runs in time O(n) for 4,5,6, ii. Now instantiate this algorithm MergeSort k for k -Vn. That is, at each step we divide a list of size n into Vn pieces of size vn, and recurse on those. (For simplicity, assume that n is of the for2 for some t so that n and n and so on is always an integer until iv. Now we have a recursive algorithm with the following properties A problem of size n gets broken up into n problems of size n . The work to run Merge-n for a subproblem of size n is O(n) by part (ii) The running time is O(n log log(n)). To see this, first notice that there are O(log log(n)) levels in the recursion tree, since that's how many times you need to take the square root of n to get down to problems of size O(1) At the 0'th level of the recursion tree, there is one problem of size n. At level 1, there are vn problems of size Vn. At level 2, there are vn -n1/4-n3/4 problems of size n14. In general, at the tth level there are n-1 problems of size n1 Thus, the amount of work at level t is O(n1-n)O(n). Thus, since there is O(n) work per layer for each of O(log log(n)) layers, the total amount of work is O(n log log(n)) This is pretty neat! Unfortunately, it's not correct. What is the problem with your friend's argument? (Don't go looking for little bugs there is a big conceptual error. The assumption that n is of the form 22 is fine.) We are expecting: An identification of which step(s) of the argument (i)-(iv) are problematic, and a clear explanation about what is wrong