GATE CSE
First time here? Checkout the FAQ!
x
0 votes
68 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 (107 points)   | 68 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

+1 vote
Best answer
answered by Boss (7.8k points)  
selected by
0 votes
i think it will be 290
answered by (27 points)  


Top Users Sep 2017
  1. Habibkhan

    7096 Points

  2. Warrior

    2574 Points

  3. Arjun

    2412 Points

  4. rishu_darkshadow

    2402 Points

  5. A_i_$_h

    2204 Points

  6. nikunj

    1980 Points

  7. manu00x

    1846 Points

  8. makhdoom ghaya

    1760 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,115 questions
33,691 answers
79,843 comments
31,098 users