1
$\begingroup$

Say we have $x$ amount of sorted arrays, each with $n$ elements, and we combine them one at a time. So merging the first two arrays would give us $2n$ in terms of cost, and $3n$ for the next array, all the way until $xn$ for the cost of merging. How would one go about finding the tightest possible Big-O bound for the cost of all the merges? I don't know how to go about this, I have tried writing an equation for the sequence, and that might be where I am going wrong. The sequence would look something like $2n+3n+4n \dots +kn = n(2+3+4+5+ \dots +k)$ and I'm not sure where to go next.

$\endgroup$
  • $\begingroup$ Are the costs exactly 2n? As for the sum, Gauss' formula? $\endgroup$ – Raphael Sep 15 '17 at 5:26
0
$\begingroup$

In case the order of the elements does not matter:

I assume your arrays are not sorted and you don't care of the order of the elements when you merge them.

If you store your arrays as a linked list, then merging list1 and list2 takes $O(1)$ time: you just point list1's tail to list2's head or vice versa depending how you are going to merge. So for $x$ arrays it wil take $O(x)$ time.

If you initially store them as $x$ separate static arrays (by static I mean their size is fixed and the arrays do not grow) then at each step you will need to create a new array of larger size to combine two previous arrays by copying each element one-by-one. Thus, initially it will take $2n$ steps, then $3n$ an so on. Then the total number of steps is $n(2+3+\dots + x) = n(\frac{x(1+x)}{2} - 1)$ which is $O(nx^2)$.

If your array is dynamic, i.e., you can append one element to the end of the arrays in $O(1)$ time, then you just append all elements to the first array in $O(nx)$ time.

In case the arrays are sorted and the order of the elements does matter:

The underlying structure does not provide an advantage, whether it is a linked list or dynamic array. Again assume that elements are stored as $x$ separate static arrays. Then we merge two arrays like in the Merge sort algorithm. The total number of steps is $n(2+3+\dots + x) = n(\frac{x(1+x)}{2} - 1)$ which is $O(nx^2)$.

But you could use the same procedure exactly like in the Merge sort algorithm by pairwise merging arrays at each stage. This will take $O(nx\log_2{x})$ time.

$\endgroup$
  • $\begingroup$ Thanks for the answer. Could you explain how you got that from that sequence? Looks like I need to go over arithmetic sequences and series' again. $\endgroup$ – Mi anta Sep 15 '17 at 3:24
  • $\begingroup$ $2+3+\dots + x = (1 + 2 +\dots + x ) - 1 = x(1+x)/2 - 1$. The sum of the first $x$ positive integers is equal to $x(1+x)/2$. $\endgroup$ – fade2black Sep 15 '17 at 3:25
  • $\begingroup$ Did you think about reduction the running time from $O(nx^2)$ to $O(nx\log_2{x})$? $\endgroup$ – fade2black Sep 15 '17 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.