Physics Forums

Physics Forums (http://www.physicsforums.com/index.php)
-   Engineering, Comp Sci, & Technology Homework (http://www.physicsforums.com/forumdisplay.php?f=158)
-   -   What is the running time of this algorithm? (http://www.physicsforums.com/showthread.php?t=583361)

zeion Mar2-12 08:43 PM

What is the running time of this algorithm?
 
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?

NascentOxygen Mar2-12 09:25 PM

Re: What is the running time of this algorithm?
 
Quote:

Quote by zeion (Post 3795718)
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
Quote:

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?

zeion Mar2-12 10:05 PM

Re: What is the running time of this algorithm?
 
Quote:

Quote by NascentOxygen (Post 3795773)
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?

rcgldr Mar3-12 12:12 AM

Re: What is the running time of this algorithm?
 
Quote:

Quote by zeion (Post 3795718)
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}?

NascentOxygen Mar3-12 12:40 AM

Re: What is the running time of this algorithm?
 
ask.com is an invaluable resource you should get to know, zeion. http://www.physicsforums.com/images/icons/icon12.gif

http://www.ask.com/web?q=how+many+comparisons+to+merge+two+sorted+lists%3F&search=&qsrc=0& o=0&l=dir

zeion Mar3-12 08:41 AM

Re: What is the running time of this algorithm?
 
Quote:

Quote by rcgldr (Post 3795937)
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.

rcgldr Mar3-12 09:15 AM

Re: What is the running time of this algorithm?
 
Quote:

Quote by rcgldr (Post 3795937)
for example {1, 3} {2, 4}? ... What about 2 lists, 3 elements each, for example {1, 3, 5} {2, 4, 6}?

Quote:

Quote by zeion (Post 3796355)
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.

zeion Mar3-12 06:08 PM

Re: What is the running time of this algorithm?
 
Quote:

Quote by rcgldr (Post 3796384)
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) ?

rcgldr Mar3-12 06:49 PM

Re: What is the running time of this algorithm?
 
Quote:

Quote by zeion (Post 3797059)
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?

zeion Mar3-12 07:57 PM

Re: What is the running time of this algorithm?
 
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:

Quote by rcgldr (Post 3797107)
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.

rcgldr Mar3-12 08:54 PM

Re: What is the running time of this algorithm?
 
Quote:

Quote by zeion (Post 3797192)
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.

zeion Mar5-12 09:39 AM

Re: What is the running time of this algorithm?
 
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?

rcgldr Mar5-12 10:23 AM

Re: What is the running time of this algorithm?
 
Quote:

Quote by zeion (Post 3799474)
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:

Quote by zeion (Post 3799474)
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?


All times are GMT -5. The time now is 04:39 AM.

Powered by vBulletin Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
© 2014 Physics Forums