Problem 1.2 Consider the following modification to the MergeSort algorithm: divi

Question

Problem 1.2 Consider the following modification to the MergeSort algorithm: divide the input array into thirds (rather than halves) recursively sort each third, and finally combine the results using a three-way Merge subroutine. What is the running time of this algorithm as a function of the length n of the input array, ignoring constant factors and lower-order terms? Hint: Note that the Merge subrontine can still be implemented so that the number of operations is only linear in the sum of the input array lengths.] a) n b) nlog n e) nilog n)? d) ne log n

Explanation / Answer

b)nlogn

Time Complexeity will be same as the last case only the log base changes to 3.

In case of 2 array splitting,we need one comparison.But for splitting into 3-way arrays needs 2 comparisions to sort.

So even after splitting array into 3,we will decrease number of passes by increasing the comparision.So

time complexity will remain same but log will get base 3 as we have splitted into 3 parts.

So time complexeity is

T(n)=3T(n/3)+ O(n) = O(nlogn) with base 3.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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