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$.
What is the worst case running time for an algorithm that combines insertionsort and mergesort?
algorithms;time complexity;runtime analysis;sorting
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.