Time complexity of merging two ordered linked lists

Question

I'm having some confusion understanding why the time complexity of merging two ordered linked lists is O(m+n).

The only way I understand that we have a time complexity of O(m+n) is we have two lists such as 1,3,5,7 and 2,4,6,8 that we grab from alternately. In this case I think that the lists need to be the same size, because if they weren't, we would have iterated through one lists completely and we can just append the remainder of the other list onto our new ordered list. But in this case, we need to iterate through each of the lists completely.

Also I think that the time complexity if we have one ordered list, L1, such that every element in it is less than all elements in the other list, L2, would be O(n) if n is the length of L1. We would never have to iterate through L2 in this case. I am wondering is my analysis of the time complexity correct? I read in other online sources that the time complexity is O(m+n) because we have two lists of length m and n respectively that we must iterate through completely. But the only time I see that happening is in the paragraph I explained above. I feel like I might be completely misunderstanding and any clarification would be appreciated.

Answer 1

The only way I understand that we have a time complexity of O(m+n) is we have two lists such as 1,3,5,7 and 2,4,6,8 that we grab from alternately.

Yes, that is one such example where you you need m+n steps.

In this case I think that the lists need to be the same size, because if they weren't, we would have iterated through one lists completely and we can just append the remainder of the other list onto our new ordered list. But in this case, we need to iterate through each of the lists completely.

This is true in the example you gave. But there are other cases where all nodes have to grabbed individually. For example, it can also happen when you merge 1,2,3,4,5,100 and 6,7,8,9.

I think that the time complexity if we have one ordered list, L1, such that every element in it is less than all elements in the other list, L2, would be O(n) if n is the length of L1. We would never have to iterate through L2 in this case.

This is true, and this would be regarded as a "best case" time complexity.

I read in other online sources that the time complexity is O(m+n) because we have two lists of length m and n respectively that we must iterate through completely.

There are different ways to speak of time complexity. When -- besides m and n -- there is variation possible in the input (in this case the actual values in the lists), we can speak of worst, average and best case time complexities. When not explicitly specified, the author may refer to the worst case time complexity, and then saying it is O(m+n) is correct, even when we know the best case complexity is O(min(m, n)).

But the only time I see that happening is in the paragraph I explained above.

There are many more cases where the worst case occurs. The common factor is that one of the lists ends with two values such that the tail of the other list should be ordered between those two. The sizes of the lists do not matter for that property to be true.

So for example:

L1: ..................... 100, 102
L2: .................. 101

It doesn't matter what is in the dots, nor how long those lists are. Just because they end this way means that there is no possibility to "shortcut" the merge operation by appending the last chunk of one list to another.

There are also many "in-between" cases, which are not the worst case, but also not the best case, i.e. where a chunk of one of the lists can be concatenated to the result without grabbing each node in that chunk separately, but where this chunk maybe only has two nodes, or three...etc.

This means that also the average time complexity will be O(n+m). This may be less evident, but the probability that a relatively large chunk of one of the lists can be concatenated without further inspection is low. It becomes lower the greater that chunk has to be.