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.
- Are these claims correct? If not, can you kindly help me understand better?
- Is there a more clearer way to reason about claims made above?
- 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.
O(n * log(k))
? surely maintaining the heap property isO(log(k))
?