CH231A-Homework Merge and Recurrences  Sort  4 Solved

Problem 4.1 Merge Sort                                                                                    
(a)     Implement a variant of Merge Sort that does not divide the problem all the waydown to subproblems of size 1. Instead, when reaching subsequences of length k it applies Insertion Sort on these n/k subsequences.

(b)     Apply it to the different sequences which satisfy best case, worst case and averagecase for different values of k. Plot the execution times for different values of k.

(c)      How do the different values of k change the best-, average-, and worst-case asymptotic time complexities for this variant? Explain/prove your answer.


(d)    Bonus  Based on the results from (b) and (c), how would you choose k in practice? Briefly explain.

Problem 4.2 Recurrences                                                                                   
Use the substitution method, the recursion tree, or the master theorem method to derive upper and lower bounds for T(n) in each of the following recurrences. Make the bounds as tight as possible. Assume that T(n) is constant for n≤ 2.

(a)     T(n) = 36T(n/6) + 2n,

(b)    T(n) = 5T(n/3) + 17n1.2,

(c)      T(n) = 12T(n/2) + n2 lgn,

(d)     T(n) = 3T(n/5) + T(n/2) + 2n,

(e)    Bonus  T(n) = T(2n/5) + T(3n/5) + Θ(n).