Consider the MergeSort algorrithm on inputs of size n = 2^k. Normall this algori

Question

Consider the MergeSort algorrithm on inputs of size n = 2^k. Normall this algorithm would have a recursion depth of k. Suppose that we modify the algorithms so that after k/2 levels of recursion, it switches over to Inserstion sort. What is the running time of this modified algorithm?


So, intuitively, I want to say O(n^2) because, if we think about splitting this, we get a run time of n log n/2 for the MergeSort (i.e. O(n log n)) and we would get a run time of (n/2)^2 = n^2/4 = O(n^2) for the insertion sort. Therefore implying the answer is just O(n^2), is this correct?

Explanation / Answer

Yes you are correct

I want to say O(n^2) because, if we think about splitting this, we get a run time of n log n/2 for the MergeSort (i.e. O(n log n)) and we would get a run time of (n/2)^2 = n^2/4 = O(n^2) for the insertion sort is correct and the answer would be O((n/2)^2) + O(n log n/2) = O(n^2)

Hope you understand. Feel free to ask any doubts. Have a nice day :)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.