Complexity of comparing elements in two lists

Question

I was coding a function in Python to find elements of a sorted list that exist in another sorted list and print out the results:

# assume that both lists are sorted
def compare_sorted_lists(list1, list2):
  res = []
  a = 0
  b = 0
  while a < len(list1) and b < len(list2):
    if list1[a] == list2[b]:
      res.append(list1[a])
      a += 1
    elif list1[a] < list2[b]:
      a += 1
    else:
      b += 1
  return res

I want to figure out the time complexity of comparing elements with this method.

Assuming that:

list1 has length A and the maximum number of digits/letters in a list1 element is X
list2 has length B and the maximum number of digits/letters in a list2 element is Y

For these lists I have O(A+B) time complexity when traversing them with pointers, but how would comparing elements affect the time complexity for this function (specifically, worst-case time complexity)?

Edit: 12 March 2021 16:30 - rephrased question

I thought that the actual worst-case time complexity for iterating and comparing both lists is along the lines of O(max(X, Y) * (A+B)). — Zhe Sheng Lim, Mar 12 '21 at 15:20
Since you have to sort both lists, the lower bound is O(N log(N)). A simpler approach is `res = set(list1) & set(list2)`. That should be no worse than O(N). https://stackoverflow.com/questions/3697432/how-to-find-list-intersection — Håken Lid, Mar 12 '21 at 15:27
You say that the time complexity of sorting does not matter, but in fact the majority of your time goes into the comparisons that are part of the sorting! You can't simply ignore your most expensive operation and hope to understand your performance! — btilly, Mar 12 '21 at 15:46
@btilly I only needed to know the time complexity for the portion of code where I find elements. I will edit my question. — Zhe Sheng Lim, Mar 12 '21 at 16:26

score 0 · Answer 1 · answered Mar 12 '21 at 16:32

0

The comparison between two elements is constant time, so this does not affect the complexity of your whole algorithm, which you corrected identified as O(A+B).

answered Mar 12 '21 at 16:32

user1717828

7,122
8
34
59

OP is in the middle of clarifying that the lists come into the function sorted already. This answer assumes he doesn't actually need to be doing any of the N*ln(N) sorting that he was initially hinting at. – user1717828 Mar 12 '21 at 16:33
That is not true for python integers for example, since they are unbounded in length. O(1) time complexity for comparison is only true for numbers represented by fixed precision (e.g. 32 bit floating numbers). See my answer https://stackoverflow.com/a/71438711/6087087. – Fırat Kıyak Mar 11 '22 at 12:44

score 0 · Answer 2 · answered Mar 11 '22 at 12:42

As user1717828 pointed out, the loop takes place at most A+B times; however comparing two elements is not a constant time operation. If the numbers are fixed point precision numbers, then yes, it is; however Python integers are unbounded. Time cost of their comparison will grow linearly with respect to the number of digits in them. Therefore the time complexity of the algorithm you gave is

O((A+B) * max{X,Y})

You can actually do better than that under specific circumstances. E.g. if A << B, then the following code has O(A*log(B)*max{X,Y}) time complexity.

for a in A:
    split B from the middle and keep searching a in B in one of the blocks. Continue 
    until you find a, or not.

because the inner loops keeps diving the list B into 2, which can last for at most log_2(B)+1 steps.

Complexity of comparing elements in two lists

2 Answers2