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$.


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.