[SOLVED] Does List Comprehension being faster than nested looping through O(n**2) code mean it has less time complexity?

Does List Comprehension being faster than nested looping through O(n**2) code mean it has less time complexity?

I have an uncertainty 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])

However, I noticed in LeetCode, List Comprehension is a bit faster. Why is this happening there if it takes the same time as nested?

A and B both have a known size, and you can assume that they are exactly the same length.

Solution

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).