Merge K sorted arrays of Length N

Question

This is the problem as stated in the book:

Suppose you are given K sorted arrays each with n elements, and you want to combine them into a single array of kn elements. You use the following approach: first merge the first and second arrays, then merge the resulting array with the third array, then the resulting with the fourth, and so on until you merge in the kth and final input array. What is the running time taken by this successive merging algorithm, as a function of k and n, ignoring constant factors and lower-order terms.

I know that the when merging the first and second arrays, I'll have at most N comparisons, then the resulting with the third array, I'll have at most 2N comparisons, then merging with the fourth array I'll have at most 3N comparisons and so on.

This results in a total of comparisons of

N + 2N + 3N + 4N + ... + (k - 1)N

however, I'm not quite sure where to go from here. I've tried looking online however they just give the arithmetic summation formula, but I don't quite understand its math and I'm not quite sure how to include k since the summation is only given in terms of n. Can anyone push me in the right direction or help me understand this better?

Thank you!

Answer 1

As I understood your problem is to sum up N + 2N + 3N + 4N + ... + (k - 1)N. That's equavalant to N*(1+2+3+...+(k-1)) = N*(k-1)*(k)/2

By the way, Note that merging two arrays of size N needs 2*N comparisons (and not N). So the correct series would be: 2N + 3N + ... + KN

S   = 2N + 3N + ... + KN
S+N = 1N + 2N + 3N + ... + KN
S+N = N (1+2+3+...+K)
S+N = N*K*(K+1)/2
S   = N*K*(K+1)/2 - N = O(N.K^2)

---

PS: We know the sum of the number from 1 to x is x*(x+1)/2

Answer 2

The tc should be O(N*k*(k-1)/2).

Also note that there is a better solution with O(k*n*lgk) solution using heap: leetcode