Register to reply 
What is the running time of this algorithm? 
Share this thread: 
#1
Mar212, 08:43 PM

P: 467

1. The problem statement, all variables and given/known data
Suppose that you have k >= 1 sorted arrays, each one containing n >= 1 elements, and you wish to combine them into a single sorted array with kn elements. 2. Relevant equations 3. The attempt at a solution Can I assume that each array has a size of n elements for a worst case scenario? Then, if I were to merge them sequentially, ie merge first two, then the third with the first two, the running time would be O(kn), since, the first two will take n comparisons, making a merged list of 2n elements, then compare to the next list of n elements takes n comparisons, and latch on the rest of the 2n list. Does that make sense? 


#2
Mar212, 09:25 PM

HW Helper
Thanks
P: 5,145




#3
Mar212, 10:05 PM

P: 467

Then I would compare 2n times and latch on the left over from the third list? I'm not sure how to set up the problem for a worst case since each array can have n >= 1 elements? 


#4
Mar312, 12:12 AM

HW Helper
P: 7,033

What is the running time of this algorithm?



#5
Mar312, 12:40 AM

HW Helper
Thanks
P: 5,145

ask.com is an invaluable resource you should get to know, zeion.
http://www.ask.com/web?q=how+many+comparisons+to+merge+two+sorted+lists%3F&search=&qsrc=0& o=0&l=dir 


#6
Mar312, 08:41 AM

P: 467

Then compare the next two, 3 and 4 and insert in the same way: (1, 2, 3, 4) Then compare 5 and 6 and get (1,2,3,4,5,6) So I compared 3 sets of 2 numbers. 


#7
Mar312, 09:15 AM

HW Helper
P: 7,033




#8
Mar312, 06:08 PM

P: 467

This will take k  1 appends? Or do I have say that I append each element at a time, so that would take n(k  1) ? Then, I suppose I will use a merge sort algorithm to sort the whole list.. which takes worstcase O(nlogn) ? 


#9
Mar312, 06:49 PM

HW Helper
P: 7,033

In this case, you have k sorted arrays of n elements each. I'm not sure what your supposed to calculate at "running time", the number of compares and moves as separate counts or the relative overhead versus k and n. Maybe one more example, merge {1, 2, 9, 10} , {4, 5, 8, 11}, {3, 6, 7, 12}. How many compares do you need? How many moves do you need? What if you merged all 3 arrays in one pass? 


#10
Mar312, 07:57 PM

P: 467

What is a "move"?
So for the example, I would "compare" the 1 with 4. Then, I will "move" the 4 between the 1 and the 2? Do I also need to "move" all of 2, 9, 10 forward to make space? 


#11
Mar312, 08:54 PM

HW Helper
P: 7,033




#12
Mar512, 09:39 AM

P: 467

Okay so,
I think, for comparing two arrays, I would always have to compare the size of the bigger array. So for the first method of combining the first two, then with the third etc.. It would take n compares for the first two, then 2n compares for the third with the first two, then 3n, then 4n ... Each time I finish comparing I would move the element to the kn array, so the moves would be 2n moves for the first two, n moves for all the other ones, so total of k moves. Does that make sense? 


#13
Mar512, 10:23 AM

HW Helper
P: 7,033

If you merged all k arrays in on pass, it would only take k x n moves. If you did merge k arrays in one pass, and assuming you haven't reached the end of any of the k arrays, how many compares would it take for each element moved to the single output array of size k x n? 


Register to reply 
Related Discussions  
Running time of an algorithm  Engineering, Comp Sci, & Technology Homework  0  
Finding total time of a running rabbit  Introductory Physics Homework  2  
Running out of Time, Please help me ASAP!  Introductory Physics Homework  4  
How fast is time running?  General Physics  8  
Is Time Running Out?  Earth  36 