Redirected
edited by
1,906 views
2 votes
2 votes
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?
edited by

4 Answers

1 votes
1 votes
Answer
1 votes
1 votes
edited by
0 votes
0 votes
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..
0 votes
0 votes
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

Related questions

0 votes
0 votes
0 answers
1
Jason_Roy asked Jan 23, 2017
303 views
How?
0 votes
0 votes
1 answer
3
Na462 asked Apr 30, 2018
4,366 views
Consider the following message:The number of bits required for huffman encoding of the above message are __________?My Strategy:- But the answer given is 52bits i used st...