There seems some ambiguity to this question. I am assuming L1 can have an interg

Question

There seems some ambiguity to this question. I am assuming L1 can have an interger in it thats greater then in L2 vise versa, therefor if L1(a1) is less then L2(a1) we cant automatically assume L1< L2

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

a)

maximum comparisons by merging L1 and L2 = 15+40-1 = 54

maximum comparisons by merging L3 and L4 = 30+60-1 =89

maximum comparisons by merging the resulted arrays = (15+40)+(30+60)-1 = 144

total = 54+89+144

b)

maximum comparisons by merging L1 and L2 = 15+40-1 = 54

maximum comparisons by merging resulting list with L3 = (15+40)+30-1 = 84

maximum comparisons by merging resulting list with L4 = (15+40+30)+60-1 = 144

total = 54+84+144

c)

we can see we should follow order of b part

d)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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