Register to reply 
Algorithm Complexity: Sorted Arrays into Sorted Array 
Share this thread: 
#1
Mar812, 02:40 AM

P: 4

1. The problem statement, all variables and given/known data
We have k >= 1 sorted arrays, each one containing n >= 1 elements (all equal length). We want to combine all of them in to a single sorted array with kn elements. We have a "naive" algorithm: merge the first two arrays, then merge the third array into the result, then merge the fourth array into the result, and so on. What's the complexity of the naive algorithm, as a function of k and n? 2. The attempt at a solution Assuming k > 1. When comparing first two arrays, worstcase requires (n log n) comparisons. Adding a third array to the resulting array has a worstcase of (2n log 2n) comparisons. Similarly, adding a fourth has (3n log 3n) comparisons. This suggests a general worstcase equation for the algorithm: (k1)n log (k1)n I don't think this is right... the next part of the question asks us to talk about a less expensive implementation, but (k1)n log(k1)n is already in big theta of n log n, which is plenty efficient. 


#2
Mar812, 04:00 AM

HW Helper
P: 7,032

You could try some simple cases and count the number of operations. I'm not sure if there's supposed to be a complexity factor for "comparing" versus "copying" data. As an example of a simple case, here are two sets of integers to be merged:
{1, 2, 5, 8, 9} and {3, 4, 6, 7, 10} What would the complexity be if each set only had 4 integers instead 5? What if each set only had 3 integers instead of 5? 


#3
Mar812, 11:53 AM

P: 4

Well, merging will happen k1 times. So the merging complexity would be (k1)n? Which is in big theta of n? (The merging part of mergesort is linear, not logarithmic, my bad).



#4
Mar812, 12:17 PM

P: 127

Algorithm Complexity: Sorted Arrays into Sorted Array
http://www.wolframalpha.com/input/?i...to+k+%28i*n%29
Reason: The first merge will take O(n+n) operations (go through both lists once). The second merge will take (2*n + n = 3n) operations (since you will have to go through the long list and once through the 3rd list. This results in an O(k^2*n) complexity. 


#5
Mar812, 12:23 PM

HW Helper
P: 7,032

I don't know how copies and compares are factored into complexity or big theta. 


#6
Mar812, 01:06 PM

P: 127




#7
Mar812, 02:35 PM

P: 4




#8
Mar812, 04:38 PM

P: 4

Shouldn't it just be kn? That's what the pattern seems to suggest.



#9
Mar812, 04:54 PM

P: 127

[tex] \sum_{i=2}^k in = n\sum_{i=2}^k i = n\frac{k^2+k2}{2} \in O(k^2*n)[/tex] 


#10
Mar812, 05:25 PM

HW Helper
P: 7,032




#11
Mar812, 06:00 PM

P: 127

Merging two lists of size n takes at most 2*n1 comparisons. In the first round you do this for k/2 lists. 


#12
Mar812, 09:12 PM

HW Helper
P: 7,032




#13
Mar912, 05:06 AM

P: 127

You can also merge them in the same way merge sort does, that will give you something like O(log(k)*k*n) worst case.



Register to reply 
Related Discussions  
Help with algorithm complexity  Engineering, Comp Sci, & Technology Homework  0  
Algorithm complexity analysis  General Math  1  
What's wrong with my sorted linked list algorithm? (Java)  Programming & Computer Science  6  
Find the median of a set of sorted lists, Computer Science  Engineering, Comp Sci, & Technology Homework  1  
Merging sorted lists  Engineering, Comp Sci, & Technology Homework  0 