In mergesort, we need to combine two sorted lists to get one sorted list. We saw
ID: 3566747 • Letter: I
Question
In mergesort, we need to combine two sorted lists to get one sorted list. We saw how to do this using the procedure merge. Suppose we instead decided to combine the two lists together by first appending the two lists into one list (i.e. the second list is added to the end of the first list) and then running insertion sort on that combined list. UNHMergeSort(array A) { if A has 0 or 1 elements then return(A) else { split A into Left and Right UNHMergeSort(Left) UNHMergeSort(Right) Do Insertion Sort on (Right appended to the end of Left).} } You can assume that n, the number of elements in the original array, is a power of 2. You have to do the following: (a) Give a recurrence relation for the running time of UNHmergesort. (b) Using the Master theorem, solve this recurrence relation.Explanation / Answer
Suppose the total length of the input lists is zero or one. Then the function must execute one of the two O(1) arms of the case expression. These take at most some time c0 to execute. So we have
T(0) = c0
T(1) = c0
Now, consider lists of total length n. The recursive call is on lists of total length n?1, so we have
T(n) = T(n?1) + c1
where c1 is an constant upper bound on the time required to execute the if statement and the operator :: (which takes constant time for usual implementations of lists). This gives us a recurrence relation to solve for T. We can apply the iterative method to solve the recurrence relation by expanding out the recurrence relation inequalities for the first few steps.
T(0) = c0
T(1) = c0
T(2) = T(1) + c1 = c0 + c1
T(3) = T(2) + c1 = c0 + 2c1
T(4) = T(3) + c1 = c0 + 3c1
...
T(n) = T(n?1) + c1 = c0 + (n?1)c1 = (c0 - c1) + c1n
We notice a pattern which the last line captures. This pattern can be proved more rigorously by induction: let us prove by induction that for n >=0, T(n)=(c0 - c1)+ c1n. For n=0, the result is true (proved above), and if it is true for n-1, it is true for n using the last line above.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.