The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
107 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?
asked in Algorithms by (181 points) | 107 views
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).
Wait I will post answer

@Ali Jazib Mahmood you are correct

2 Answers

+2 votes
Best answer
answered by Veteran (10.6k points)
selected by
0 votes
i think it will be 290
answered by (121 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,946 questions
36,792 answers
91,049 comments
34,688 users