What is the running time of this algorithm?

In summary: I compare the first two lists of n and n elementsthen I compare the next list of n and 2n elementsthen I compare the next list of n and 3n elementsand I continue to add n for each succeeding list, soI compare n, 2n, 3n, 4n, ..., kn elementswhich is n * (1 + 2 + 3 + ... + k)= n * (k(k+1)/2)= n * (k^2 + k)/2= O(nk^2)In summary, the worst-case running time for merging k sorted arrays, each with n elements, into a single sorted array with kn elements, is
  • #1
zeion
466
1

Homework Statement



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.


Homework Equations





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?
 
Physics news on Phys.org
  • #2
zeion said:
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?
 
  • #3
NascentOxygen said:
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?
 
  • #4
zeion said:
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}?
 
Last edited:
  • #6
rcgldr said:
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.
 
  • #7
rcgldr said:
for example {1, 3} {2, 4}? ... What about 2 lists, 3 elements each, for example {1, 3, 5} {2, 4, 6}?

zeion said:
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.
 
Last edited:
  • #8
rcgldr said:
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) ?
 
  • #9
zeion said:
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?
 
Last edited:
  • #10
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?

rcgldr said:
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.
 
  • #11
zeion said:
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.
 
  • #12
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
zeion said:
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}?

zeion said:
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?
 

What is the running time of this algorithm?

The running time of an algorithm refers to the amount of time it takes for the algorithm to execute and complete its task.

How is the running time of an algorithm measured?

The running time of an algorithm is typically measured in terms of the number of operations or steps it takes to complete its task. This can be expressed as a function of the input size, such as O(n) or O(n^2), where n represents the size of the input.

What factors affect the running time of an algorithm?

The running time of an algorithm can be affected by a variety of factors, including the size and complexity of the input, the efficiency of the algorithm design, and the hardware and software environment on which the algorithm is executed.

Why is it important to consider the running time of an algorithm?

The running time of an algorithm is important because it can impact the overall performance and efficiency of a program. A more efficient algorithm can save time and resources, making it a crucial consideration in many applications.

Can the running time of an algorithm be improved?

Yes, the running time of an algorithm can often be improved through algorithmic optimizations and improvements in hardware and software environments. However, the running time can also be limited by the inherent complexity of the problem being solved.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
12
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
21
Views
2K
  • Programming and Computer Science
Replies
4
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
10
Views
2K
Replies
9
Views
942
  • Engineering and Comp Sci Homework Help
Replies
8
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
17
Views
5K
Back
Top