patternMinor
What is the worst case running time for an algorithm that combines insertionsort and mergesort?
Viewed 0 times
casethecombinesmergesortwhatinsertionsorttimealgorithmrunningthat
Problem
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$.
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$.
Solution
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.
$$ 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.
Context
StackExchange Computer Science Q#41479, answer score: 2
Revisions (0)
No revisions yet.