The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes
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 (205 points) | 237 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'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

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

combine 65 & 70 to give will take 135 units of time.
combine75 & 80 to give will take  155units of time.
at last combine 155&135 to give 290 sized 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

+3 votes
Best answer
answered by Boss (15.9k points)
selected by
0 votes
i think it will be 290
answered by (125 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

35,520 questions
42,844 answers
42,191 users