Ok I see your point, I thought that it asked to provide an algorithm with overall complexity O(logn), which is not possible.
why not use a binary search like procedure to fix the worst case. Choose the array lets say list L with the bigger number, then instead of checking each element of smaller list S one by one, execute binary search in S for the number in L_1. This will find the index of items smaller than L_1, insert them to the merged array, and L_1. repeat this untill all elements are processed. While this involves a single item only O(logn) times, the overal complexity of merge is still O(n) because the items should be copied in any case. On Nov 8, 12:01 pm, Terence <technic....@gmail.com> wrote: > No. It is possible. > > This problem focuses on comparisons of each element. > The overall time complexity of merge operation can be as high as O(nlogn), > while the normal merge operation has time complexity O(n). > > But the normal merge operation does not meet the requirement, since in > the worst case, (the largest number in one sequence is smaller than the > smallest of the other), one element can be included in n comparisons at > most. > > On 2010-11-8 17:00, G nen Ercan wrote: > > > > > > > > > does not seem possible, there is a proof that shows that comparison > > based algorithm can have at best O(nlogn) worst case running time. You > > can check this proof from algorithms CLRS book. > > > Using this proof, by master's theorem if the merge operation can be > > implemented in O(lgn) using merge sort with this merge operation, the > > complexity would be O(logn) contradicting with O(nlogn). > > > So I think its not possible to design such merge algorithm. > > > On Nov 8, 4:58 am, lichenga2404<lichenga2...@gmail.com> wrote: > >> Suppose we'd like to implement a sorting variant where every element > >> is compared only a small number of times. > >> a) devise a divide and conquer algorithm to merge 2 sorted arrays of > >> length n , which guarantees that every element is included in at most > >> O(log n ) comparisons. > >> b) using this modified merge , prove that Merge-Sort will include > >> element in at most O( (log n)^2) comparisons. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
