This is my second time posting this, and I am not getting much activity on this.

Question

This is my second time posting this, and I am not getting much activity on this. Im raising the points, well actually all the points I have left. I really hope someone can help me out on this problem. I am assuming the maximum number of comparisons would be 145 for both part a and b, but this seems more intuitive then that. I am also assuming L1 can have an integer in it thats greater then in L2 vise versa. Therefor if L1(a1) is less then L2(a1) we cant automatically assume L1 < L2. Hope I can find some kind enough to answer this problem for me. Thanks in advance!!!!

Suppose we want to merge a group of already ordered lists L1, L2, L3, and L4 with sizes 15, 40, 30, and 60. respectively. What is the maximum number of comparisons made by merging L1 and L2, merging L3 and L4? and then merging the resulting lists? What is the maximum number of comparisons made by merging L1 with L2, merging that list with L3, and then merging with L4? In order to minimize the (worst-case) number of comparisons, what order should the lists be merged in? If given lists L1,..., Ln, how could one construct a merging tree that minimizes the worst-case number of comparisons? (Your answer should be one sentence.)

Explanation / Answer

If the list is sorted than you only need the sum of the two list comparisions in worst cases

eq - L1 - 1 3 5 7 9

L2 - 2 4 6 8 10

no of comparisions = 5 + 5 = 10 - 1

then you need maximum comparision = L1 + L2 = 15 + 40 - 1 = 54

and L3 + L4 = 30 + 60 - 1 = 89

so total = 89 + 54 = 143

and in 2nd case L1 + L2 = 15 + 40 -1 = 54

then L1 + L2 + L3 = 54 + 30 - 1 = 83

and finally L1 + L2 + L3 + L4 = 83 + 60 - 1= 142

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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