There is a leetcode question about merging k sorted arrays. I would like to be able to explain the time complexity of the following **naive** solution:

`function mergexsSortedArrays(xs) { if (xs === null || xs.length === 0) { return []; } let l1 = xs[0]; for (let i = 1; i < xs.length; i++) { let l2 = xs[i]; l1 = merge(l1, l2); } return l1; } /* This is simply for completeness; the relevant code is above /* function merge(l1, l2) { const ans = []; let l1HeadIdx = 0; let l2HeadIdx = 0; while (l1HeadIdx < l1.length && l2HeadIdx < l2.length) { if (l1[l1HeadIdx] < l2[l2HeadIdx]) { ans.push(l1[l1HeadIdx]); l1HeadIdx++; } else { ans.push(l2[l2HeadIdx]); l2HeadIdx++; } } while (l1HeadIdx < l1.length) { ans.push(l1[l1HeadIdx]); l1HeadIdx++; } while (l2HeadIdx < l2.length) { ans.push(l2[l2HeadIdx]); l2HeadIdx++; } return ans; } `

Let’s say that `k`

is the number of elements in the input array. To simplify the math, we will assume that each sorted array has length `n`

.

Within the for loop, we are running the merge algorithm. On the first iteration, `l1`

will have length `n`

and `l2`

will have length `n`

, so the merge algorithm will be do `2n`

work. In the second iteration, `l1`

will be `2n`

and `l2`

will be `n`

, so merge will do `3n`

work. As our result, the amount of work that is being done in our for loop will be `2n + 3n + 4n ... (k - 1) n`

. If we expand this work a bit, it would be `n + 2n + 3n ... k(n)`

, and this can be re-written as `n * (1 + 2 + 3 ... k)`

; the inner sum has a closed-form formula of `[k * (k + 1)] / 2`

, which is essentially an `O(k^2)`

, and then we add the `n`

to get a final time complexity of `O(n(k^2))`

.

Is this correct? Or have I gone off the rails?