Introduction to Algorithms. Exam Study Questions. Although merge sort runs in B(

Question

Introduction to Algorithms. Exam Study Questions.

Although merge sort runs in B(n lg n) worst case time and insertion sort, nms in (n^2) worst case time, the constant factors in insertion sort make it faster for small n. Thus, it makes sense to use insertion sort within merge sort when sub problems become sufficiently small. Consider a modification to merge sort in which n/k sublists of length k are sorted using insertion sort mid then merged using the standard merging mechanism, where k is a value to be determined. Show that n/k sublists, each of length k. can be sorted by insertion sort in B[nk] worst case time. Show that the Niiblists ran be merged in B(nlg(ri/Xr)) worst case time. Given that the modified algorithms runs in (nA + nlg(n/fc)) worst case time, what is the largest asymptotic (9-notation) value of A as a function of n for which the modified algorithm has the same asymptotic worst case running time as standard merge sort? How should k should be chosen in practice?

Explanation / Answer

a)

2.

This step is just merge-sort which normally takes (n lg (n)) time because at the deepest level of recursion there are n single-element lists which must be merged, but, since we have already sorted n/k k-element lists, we start with n/k lists to merge which can be done in (n lg (n/k)) time.

3.T(nk + n lg (n/k)) = (n lg n). To discover the largest value of k which allows this, observe that, because of the nk term, k (lg n) otherwise nk > (n lg n) which would make T(nk + n lg (n/k)) > (n lg n) which contradicts what we want. Let k = (lg n), then we have T(nk + n lg (n/k))
= (n lg n + n lg (n/lg n))

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.