You have an algorithm MergeSort3 that breaks a list into three parts, performs merge sort on them, and then merges them. This run time is O(nlogn), which makes sense to me, what doesn't make sense is why the MergeSort_k below would be problematic and not fit this mold. The actual question I need answered is at the bottom, a thorough laymen's terms explanation would be appreciated

Below is the description of a problematic MergeSort_k that your friend has thought of in light of the basic properties of MergeSort3. Why is this problematic?

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