2 votes 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? Algorithms algorithms merging numerical-answers + – Ali Jazib Mahmood asked Aug 18, 2017 retagged Jul 7, 2022 by Lakshman Bhaiya Ali Jazib Mahmood 1.3k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Ali Jazib Mahmood commented Aug 18, 2017 reply Follow Share 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. 0 votes 0 votes Tesla! commented Aug 18, 2017 reply Follow Share They are correct it is not similar question, here it is asked time and there it was asked number of comparison. 0 votes 0 votes Ali Jazib Mahmood commented Aug 18, 2017 reply Follow Share 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). 0 votes 0 votes Tesla! commented Aug 18, 2017 reply Follow Share Wait I will post answer 0 votes 0 votes Tesla! commented Aug 18, 2017 reply Follow Share @Ali Jazib Mahmood you are correct 0 votes 0 votes smsubham commented Feb 26, 2018 reply Follow Share good read: https://xlinux.nist.gov/dads/HTML/optimalMerge.html 0 votes 0 votes Please log in or register to add a comment.
Best answer 3 votes 3 votes total time would be 25+65+135+155+290=670 some similar reference:https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_optimal_merge_pattern.htm https://gateoverflow.in/1997/gate2014-2-38 Tesla! answered Aug 18, 2017 selected Aug 19, 2017 by Ali Jazib Mahmood Tesla! comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes i think it will be 290 sh2mohit111 answered Sep 10, 2017 sh2mohit111 comment Share Follow See all 0 reply Please log in or register to add a comment.