[Solved]: What is the worst case running time for an algorithm that combines insertionsort and mergesort?

Problem Detail: 

Suppose that we have an algorithm "combination" that uses insertionsort for $n < 100$ and mergesort for $n \geq 100$. Is the worst case running time of "combination" then $n^2$ or $n\log n$?

I was thinking that it's simply $n^2$, since the algorithm "combination" allows inputs larger than 100, in which case the worst case running time is $n^2$.

Asked By : Ken

Answered By : Yuval Filmus

In fact, the running time of mergesort for large $n$ doesn't depend on what happens for small $n$. Recall the recurrence for mergesort:

$$ T(n) = 2T(n/2) + O(n), \qquad T(1) = O(1). $$

This recurrence holds even if you run insertion sort for $n < 100$, since the running time of insertion sort on at most 100 elements can be swallowed in the big O constants. Even if you use exhaustive search on all $n!$ permutations for $n < 100$, mergesort will still run in time $O(n\log n)$; the only change is that the big O constant would be rather huge.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41479