Can anyone please explain the Complexity of this line?

Question

I'm facing trouble calculating the time complexity of this line. It seems Quadratic O(n**2) to me. Because I have to go through nested loop here if I don't use list comprehension.

    AB = Counter([(a+b) for a in A for b in B])

Answer 1

Your line:

AB = Counter([(a+b) for a in A for b in B])

is equivalent to (ignoring the fact that the list comprehension is faster and does not append one by one*):

# given lists A, B
AB0 = []

# this is O(n2)
for a in A:
    for b in B:
        AB0.append(a+b) 

AB = {}

# this is O(m), m=n2
for ab in AB0:
    if ab not in AB:
        AB[ab] = 0
    AB[ab] += 1

• about the difference with the list comprehension: the comprehension implementation is faster (explained here), but this does not mean that it has a different time complexity than O(n2). Also: append is O(k).

So all in all, it is bounded by O(n2).