# What is the running time of this algorithm?

by zeion
Tags: algorithm, running, time
 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?
HW Helper
Thanks
P: 5,356
 Quote by zeion 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,
okay
 then compare to the next list of n elements takes n comparisons, and latch on the rest of the 2n list.
What if there is no "rest"? Maybe the n list has elements to be slotted throughout the 2n list?
P: 467
 Quote by NascentOxygen okay What if there is no "rest"? Maybe the n list has elements to be slotted throughout the 2n list?
So you're saying, if the third list had more than 2n elements?
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?

HW Helper
P: 7,131
What is the running time of this algorithm?

 Quote by zeion If I were to merge them sequentially, ie merge first two, then the third with the first two ... 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
Are you sure it only takes n compares to merge two arrays of size n? Take a very simple case, how many compares does it take to merge 2 lists with 2 elements each, for example {1, 3} {2, 4}? What about 2 lists, 3 elements each, for example {1, 3, 5} {2, 4, 6}?
 HW Helper Thanks P: 5,356 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
P: 467
 Quote by rcgldr Are you sure it only takes n compares to merge two arrays of size n? Take a very simple case, how many compares does it take to merge 2 lists with 2 elements each, for example {1, 3} {2, 4}? What about 2 lists, 3 elements each, for example {1, 3, 5} {2, 4, 6}?
So for the second example, I would compare 1 and 2, then insert the smaller one, then insert the larger one: (1, 2)

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.
HW Helper
P: 7,131
 Quote by rcgldr for example {1, 3} {2, 4}? ... What about 2 lists, 3 elements each, for example {1, 3, 5} {2, 4, 6}?
 Quote by zeion So for the second example, I would compare 1 and 2, then insert the smaller one, then insert the larger one: (1, 2) 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.
Using this same method how would you merge {1, 2, 5} and {3, 4, 6}? By "insert" do you mean to "insert" into the output array? If so that's not a merge, and if insertion was used, the insertion would take more compares.
P: 467
 Quote by rcgldr Using this same method how would you merge {1, 2, 5} and {3, 4, 6}? By "insert" do you mean to "insert" into the output array? If so that's not a merge, and if insertion was used, the insertion would take more compares.
Okay so, to "merge" two lists I will simply append either one after the other.
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 worst-case O(nlogn) ?
HW Helper
P: 7,131
 Quote by zeion Then, I suppose I will use a merge sort algorithm to sort the whole list.. which takes worst-case O(nlogn)?
That's the time it takes to sort a single unsorted array of n elements, and O(...) is a relative number, the (n log n) shows how the number of elements affects O(...), without separating moves and compares (there are fewer compares than moves).

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?
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?

 Quote by rcgldr 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.
The questions says, "What is the worst-case running time of this algorithm, as a function of k and n?" The algorithm being to merge the first list with the second, then that one with the third.. etc.
HW Helper
P: 7,131
 Quote by zeion What is a "move"?
OK, apparently merging wasn't explained to you properly in class. A merge of k arrays, each of of size n, ends up copying the data into a new single array of size k x n. So there's a total of k+1 arrays involved, the k input arrays of size n each, and the output array of size k x n.
 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?
HW Helper
P: 7,131
 Quote by zeion I think, for comparing two arrays, I would always have to compare the size of the bigger array.
How many compares would you have to do to merge {1, 2, 9} and {3, 4, 5, 6, 7, 8}?

 Quote by zeion 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.
If you merged 2 arrays into an output array, you would need another array to merge that output array with the 3rd input array, alternating between the two output arrays. That would require (2 + 3 + ... + k) x n moves.

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?

 Related Discussions Engineering, Comp Sci, & Technology Homework 0 Introductory Physics Homework 2 Introductory Physics Homework 4 General Physics 8 Earth 36