+1 vote
166 views
To merge 2 files of size m and n it takes m + n time What will be the optimal time Complexity to merge the files of size 10, 15, 40, 70, 75 and 80?
Answer is 290,but I have 670.
I dont think its 290 because its list's total size.No matter what pattern you take(optimal or not) list size will be 290.
670 will be the total time taken and question is asking for time not final size.
It was a question on testbook.com's test.
just want to know whether my approach is right or not.
They are correct it is not similar question, here it is asked time and there it was asked number of comparison.
but sir can you elaborate please,how time complexity is different from number of comparisions(only in this case).
As far as i understand OMP:

we'll combine 10 and 15 sized lists to give 25 sized list,it will take 10+15 units of time
then

combine 25 and 40 sized lists to give 65 sized list. it will take 65 units of time.
then

combine 65 & 70 to give 135.it will take 135 units of time.
combine75 & 80 to give 155.it will take  155units of time.
at last combine 155&135 to give 290 sized list.it will take 290units of time.
this is something optimal,any other combination will take more time.So,in total 670units of time.
Now if I assume they are correct and it actually takes 290units of time,that means each list is contributing one element at every merge it is a 6 way merge(or n-way merge in general).

Can you please break the time taken in every merging of list please?
(This the most elaborately I can state my confusion).

@Ali Jazib Mahmood you are correct

total time would be 25+65+135+155+290=670

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

selected
i think it will be 290