How to reason about complexity of Merging k sorted linked lists?

Question

I am trying to understand Big O notation better to be able to reason about it in a much clearer way and therefore, need some feedback on my analysis given below for problem: Merge k-sorted linked lists into one.

Claim #1:

var merge2Lists = function(list1, list2) {
        if (!list1) {
            return list2;
        }
        if (!list2) {
            return list1;
        }

        if (list1.val <= list2.val) {
            list1.next = merge2Lists(list1.next, list2);
            return list1;
        }
        else {
            list2.next = merge2Lists(list2.next, list1);
            return list2;
        }
    };

merge2Lists mentioned above is used by both solutions given below. Complexity of this function should be O (n1 + n2) where n1 and n2 are number of elements in list1 and list2 respectively. Or we can just say that in worst case both lists will have equal number of elements and we will have to go over all of them at least once, so we can call it O(n).

Claim #2

// Solution: 1
var mergeKLists = function(lists) {
    let len = lists.length, interval = 1, i;
    while (interval < len) {
        for (i = 0; i < len; i += interval*2) {
            lists[i] = merge2Lists(lists[i], lists[i+interval])
        }  
        interval *= 2;
    }
    return (len > 0) ? lists[0]: lists;
}

Say I have 10 lists in my input which are to be merged. My solution above takes those 10 lists and in first iteration of the while loop, it merges 10/2 = 5 pairs. In next iteration, it merges 10/4 = 3 pairs. Next it merges 10/8 = 2 pairs and then finally we have our final sorted list at lists[0].

As number of pairs to be merged is getting halved at each step, its time complexity should be log(k), where k is the number of lists in the input. Another way to describe it can be that, if we double the input size (i.e. from 10 to 20) then the number of operations increased will not be double which means its definitely not O(n). Number of operations may only increase by 1, which means it should be log(k).

Together with Claim 1, total complexity should becomes: O (n * log k). I don't know how to explain this clearly though.

Space complexity should be O(1) as our memory stays constant with respect to input size.

Claim #3

// Solution: 2
var mergeKLists = function(lists) {
    let len = lists.length;
    if (!len) return lists;

    while (lists.length > 1) {
        lists.push(merge2Lists(lists[0], lists[1]));
        lists.shift();
        lists.shift();
    }
    return lists[0];
};

Here mergeKLists is merging only 1 pair in each iteration of the while loop. If we have 10 lists, after first iteration we would have merged only 1 pair. In second iteration we will merge another pair and so on. So it seems like we are doing 10 operations in total. So its complexity should be O (k) where k is the number of lists in input.

If we double the size of input from 10 to 20, number of operations increased will be 10 which is in line with our deduced complexity of O(k).

More over we are using shift() function 2 times to discard non-needed lists from the array. Complexity of shift() itself is O (m) where m is the number of elements in the array shifted. In worst case, shift will have to shift m elements to left. So time complexity for this solution will become O (k + m).

Together with Claim #1, total complexity should become: O (n * (k+m)).

Space complexity should be O(1) as for each new element being pushed into the array we discard to elements from the array i.e. space acquired is not increasing on with respect to input.

1. Are these claims correct? If not, can you kindly help me understand better?
2. Is there a more clearer way to reason about claims made above?
3. I noticed that at least on LeetCode Solution #2 ran 30ms faster than Solution #1 for same set of test cases. Can it be just a LeetCode bug or Network Latency as I expected Solution #1 to run much faster due to its log(k) time complexity.

Answer 1

CLAIM 1

Claim 1 looks right (but the code there could be simplified replacing if (list2.val < list1.val) with 'else'. I would also comment in the code someplace that you are joining the lists intrusively - changing the incoming arguments in place.

CLAIM 2:

This part I think you have right, but explained poorly. When you said "ts time complexity should be log(k), where k is the number of lists in the input" I was very confused. You mean that you go through that loop log(k) times, but the time for each (inner loop) is bounded (from above) by O(N) where N is the SUM of the lengths of all the lists (since you don't know which lists you will be operating on).

Also - I never saw where you clearly defined 'n' but i assume by n you mean SUM n(sub-i).

CLAIM 3:

Introducing a new variable 'm' here is not a good idea. It's bounded from above by 'n' and changes each time through the loop (so not a function of the problem but of the solution), so its not a good candidate to do analysis on.

You are right that you look through k times. And if we continue to assume 'n' is the sum of the lengths of all the lists, then n is an upper bound on the lengths of each of the two lists argument to merge.

And if we assume your 'lists' is implemented using a vector (it doesn't need to be and would be more performant if it too was a linked list), then the total complexity becomes

O (K*k) (for the shifts of the array of length k done k times) PLUS O (k * N) for the k merges.

Or - O (k*(k+n))

BTW - if you use a linked-list for 'lists' - it becomes O(k*n) - because the linked list operations - pushing to the front and popping from the front - are all O(1).