Please explain a, b, c, and d. Midterm Exam 9. It has been determined that the M
ID: 3740434 • Letter: P
Question
Please explain a, b, c, and d.
Midterm Exam 9. It has been determined that the MERGR-SORT algorithm can be expected to run in (n lg n) Thursday, 22 February 2018 time whereas INSERTION-Soler runs in (worst case) err) time. On the other hand, INSERTION SoRT does sort in place and has a fairly low constant or overhcad Mincn time. Meanwhile, MERGE-SORT requires up to Ig n additionalp storage space and requires a high time constant to set up. That is, for 3 Mica small values of n. INSERTION-SORT is to be preferred MERGE SoRTLA, p, g) 4 MERGE-SoaA, 1, r) )2 We could envision a variation of MERGE-SORT which uses the algorithm (shown) but rather than recursive calls to MERGE MiRata, p, g SORT uses IsSERTION-SORT instead as the sorting technique. That , given an input list of n values, the list is broken into sub-lists, each of 3 let 1 size k; there will be [n/k] such sub-lists in total. Then each sub-list is sorted by calls to INSERTION-SORT which is not costly since the liato% relatively small. Finally, the sorted sub-lists are put back together 6 for i- 1 to n with the MERGE procedure. For this to work, the value k is 17,RI];A[y+? be new arrays lists are 5 L AP+11 determined in advance. 10 i-1 12 for k p to r a. (6 points) Show that the n/k sub-lists, each of length k, can be b. (6 points) Show that the sub-lists can be merged in ?(n lg(n/k)) 1? +1 c. (3 points) As k gets big, this modification loses its value, until when k n, we have one sorted by INSERTION-SORT in ?(nk) worst-case time 16 else A[k]-RUI worst-case time sub-list of length n and we are no better off than before. Since the INSERTION-SORT takes ?(nk) time and the MERGE takes ?(n lg(n/k)) time, the modified algorithm requires ?(nk + n Ig(n/k)) time overall. What is the largest value of k which would make this approach beneficial? d. (3 points) How would you recommend choosing the value of k given an input list size n? Continue on the next page » CS303 Algorithms and Data Structures 4 of 5Explanation / Answer
a. For sorting each list, it takes ak2 +bk +c for constants a, b and c. We have n/k of those, hence:
n/k(ak2 + bk + c) = ank + bn +cn/k= ?(nk)
b. Sorting a sublist of length k each takes:
T(a) = 0 if a = 1;
T(a) = 2T(a/2) + ak if a = 2p; if p > 0:
Since merging one sublist is trivial and merging ‘a’ sublists means dividing them in two groups of a/2 lists, merging each group recursively and then combining the results in ak steps, since we have two arrays, each of length a/2k.
Proof:
T(1) = 1k lg 1 = k.0 = 0
Assume that T(a) = ak lg a and we calculate T(2a):
T(2a) = 2T(a) + 2ak = 2(T(a) + ak) = 2(ak lg a + ak) = 2ak(lg a + 1) =
=2ak(lg a + lg 2) = 2ak lg(2a)
Now if we substitute the number of sublists n/k for a:
T(n/k) =(n/k) k lg(n/k) = n lg(n/k)
While this is exact only when n/k is a power of 2, it tells us that the overall time complexity of the merge is ?(n lg(n/k)).
c. The largest value is k = lg n. If we substitute, we get:
?(n lg n + n lg(n/lg n))= ?(n lg n)
If k = f(n) > lg n, the complexity will be ?(nf(n)), which is larger running time than merge sort.
d. Conventionally, the largest list length for which insertion sort is faster than merge sort should be k.