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 $nlog 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(nlog 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
