Register to reply

What is the running time of this algorithm?

by zeion
Tags: algorithm, running, time
Share this thread:
zeion
#1
Mar2-12, 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?
Phys.Org News Partner Science news on Phys.org
Physicists discuss quantum pigeonhole principle
Giant crater in Russia's far north sparks mystery
NASA Mars spacecraft prepare for close comet flyby
NascentOxygen
#2
Mar2-12, 09:25 PM
HW Helper
Thanks
P: 5,145
Quote Quote by zeion View Post
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?
zeion
#3
Mar2-12, 10:05 PM
P: 467
Quote Quote by NascentOxygen View Post
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
#4
Mar3-12, 12:12 AM
HW Helper
P: 7,033
What is the running time of this algorithm?

Quote Quote by zeion View Post
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
#5
Mar3-12, 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
zeion
#6
Mar3-12, 08:41 AM
P: 467
Quote Quote by rcgldr View Post
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
#7
Mar3-12, 09:15 AM
HW Helper
P: 7,033
Quote Quote by rcgldr View Post
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 View Post
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
#8
Mar3-12, 06:08 PM
P: 467
Quote Quote by rcgldr View Post
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
#9
Mar3-12, 06:49 PM
HW Helper
P: 7,033
Quote Quote by zeion View Post
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
#10
Mar3-12, 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?

Quote Quote by rcgldr View Post
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
#11
Mar3-12, 08:54 PM
HW Helper
P: 7,033
Quote Quote by zeion View Post
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
#12
Mar5-12, 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?
rcgldr
#13
Mar5-12, 10:23 AM
HW Helper
P: 7,033
Quote Quote by zeion View Post
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 View Post
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?


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