Testbook Test Series: Algorithms - Greedy Algorithm

Question

The optimal time required in merging the list of size 11, 21, 33, 34,45,54,60 is

my answer (11+21)*4+ 33*3 +(34+45)*3 + (54+60)*2

but the provided answer is 269 to 282

I don't think I have solved it wrong but just want to confirm is there any other way to do this?

Comments

can u please explain how u are geting number of comaprision ???\

---

acording to me its no. of camprisiom ..!

if i am wrong then please correct me

---

Same question with answers:

https://gateoverflow.in/109510/optimal-time-for-merging-lists-testbook-test-series-2

https://gateoverflow.in/144698/optimal-merging

Answer 1

Answer

Comments

@skraj At level 3 b/w 65 79 54 60 you considered 54 and 65 why? it should be 54 and 60?

Answer 2

Total Time=32+65+79+114+144+258=962 units 

we have to count weights of internal nodes 

similar reference:https://gateoverflow.in/1997/gate2014-2-38

https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_optimal_merge_pattern.htm

Comments

I think someone hides his answer but @Tesla! there was a confusion going on @joshi_nitish was counting the weights of nodes as well. But from my point of view, I think 258 is correct because we don`t consider weights until and unless moves are mentioned ,So could you please sort it out?

---

thanks ..nyc way to solve

---

258 is not answer 434 is

---

258 being one of the internal node adding 258+434=692 which is the answer

Answer 3

11,21,33,34,45,54,60

First add 11+21=32

Arrange in order

32,33,34,45,54,60

Add first 32+33=65

Arrange in order

34,45,54,60,65

Add first two 34+45=79

Arrange in order

54,60,65,79

Add first two 54+60=114

65,79,114

Add first two 65+79=144

Arrange in order

114,144

Add 114+144= 258..

Comments

Shouldn't it be the total no of comparisons than the total no of movements?

Answer 4

answer is asking in terms of complexity as it has given time complexity to be o(n+m), 692 is total record movement and yes we will be comparing 692 times but in terms of worst case we will be seeing during the full execution cycle what is the maximum number of comparison and that will be the complexity.

cosider 3- for loop in some function

one for loop iterate from 0 to n;

seconde iterate from 0 to m;

and other iterate from 0 to m+n;

so we write the complexity as o(m+n);

same thing happening with the optimal merge pattern we merge list  (11 and 21)  then (32 and 33)... and last (198 and 60)

consider  all this iteration and write the worst case senario it will be 198+60 that why i think the aswer is 258