Time complexity of algorithm which merges a stack of linked lists

Question

I'm trying to find the complexity (in big O notation) of the following pseudocode, in terms of k and n.

d is a stack of size n, and each element in the stack is a linked list of length k. The merge function runs in O(a + b) time where a and b are the lengths of the two linked lists it is merging.

while d.size >= 2
    L = d.pop()       // O(1) 
    L1 = d.pop()      // O(1)
    L2 = merge(L, L1) // O(a + b)
    d.push(L2)

Answer 1

The time complexity is O(kn²), where n is the size of the original stack. To see why, think about the lengths of the lists that are merged; the result of the previous merge is always on top of the stack, so it is always one of the lists which is merged next:

• The first merge is of length k + k = 2k.
• The next merge is of length 2k + k = 3k.
• The next merge is of length 3k + k = 4k.
• ...
• The final merge is of length (n-1)k + k = nk.

The running times of the merge operations are proportional to the lengths of the resulting lists after merging, so we can add those up:

2k + 3k + 4k + ... + nk = k × (2 + 3 + ... + n) = k × ((n² + n)/2 - 1)

Discarding the dominated terms and the constant factor of 1/2 gives O(kn²). Note that the sizes of the computations actually increase as the loop continues; on later iterations, more data is being merged, not less.

---

For intuition, you should expect the time to be quadratic in the number of lists for the same reason that naively concatenating strings together takes quadratic time in the number of strings.

As an aside, if you use a queue instead of a stack then this takes O(kn log n) time instead. I'll leave you with that to think about!