Optimal Merge Pattern

Question

What will be the time complexity to obtain optimal merge pattern to merge files using greedy technique?

Comments

The technique is same as the one we follow for Huffman tree.
Good read: https://xlinux.nist.gov/dads/HTML/optimalMerge.html

---

Can you tell about optimal merge pattern space complexity?

Answer 1

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(n²).
 

Comments

Can u explain how it works??

Actually i wanted to know whether you consider the time of merge procedure??

If we consider tie for merging then it should be n2.

---

No i am not considering the merging procedure.
Optimal merge pattern gives you that in which order you need to combine (2-way) two files so that no of record movements are minimum in a single sorted file.

---

Got it!

Thanks!

---

its welcome

Answer 2

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)

Comments

what about the time taken to merge those extracted lists? both lists will have variable length and for every iteration merge time will be different so how can you say it?

Answer 3

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)

Comments

I wanted to know why you not considering the merge time??