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<[email protected]> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
