retagged by
10,068 views
0 votes
0 votes
What will be the time complexity to obtain optimal merge pattern to merge files using greedy technique?
retagged by

3 Answers

2 votes
2 votes

If we implement Heap to get the minimum sized file,
the time complexity is O(nlogn),
If we use simple list and perform linear search to get the minimum sized file, the time complexity is O(n2).
 

1 votes
1 votes
we can construct a min heap of both the files and compair both the min element and using  we can add the sum of both the minimum elements , bu using this processes ve can do this work in nlogn time.

Time taken-

 1) construct a min heap=o(n) time

2) take 2 min element =o(logn) time

and add them insert into the array (this process will be repeated n-1 times)

insert o(logn)(this will repeat n-1 times)

so total time taken will be o(nlogn)
0 votes
0 votes
We can use min heap tree to merge files to obtain optimal merge pattern in Greedy technique.

Time Complexity-

time taken to create min heap tree of given records= O(n)

From min heap, every time two minimum element will be deleted(2 log n) and their sum will be inserted(log n) after merging. It will continue upto (n-1)times

So T(n)= n + (n-1) 3 log n

            =n + n log n = O(n log n)

Related questions

5 votes
5 votes
1 answer
1
Shashank Chavan asked Dec 15, 2015
2,131 views
In Optimal merge pattern when do we get more than one tree(Sub trees) when creating a merge pattern?Can you explain/draw optimal merge tree for n=7, <8,15,3,10,20,2,30>
2 votes
2 votes
1 answer
2
VIKAS TIWARI asked Dec 13, 2017
3,821 views
Given a set of sorted files f1,f2,f3,f4,f5 of lengths 99,27,71,199,259 we need to merge these files into a single sorted file Using Optimal Merge Pattern.
2 votes
2 votes
2 answers
3
Ali Jazib Mahmood asked Aug 18, 2017
1,340 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?
0 votes
0 votes
2 answers
4