0

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])
satta sunder talukder
  • 41
  • 4
  • It is indeed O(n**2) for the exact reason that you stated. Why are you confused? – thornejosh Mar 27 '21 at 15:03
  • Cause I noticed in LeetCode List Comprehension is a bit faster. Why is this happening there if it takes same time as nested? BTW, thanks a bunch for your response. – satta sunder talukder Mar 27 '21 at 15:07
  • When code X is faster than Y, then you cannot conclude that X has a better time complexity than Y. It does not follow. It could even turn out that X has a worse time complexity than Y. – trincot Mar 27 '21 at 15:12
  • Does either A or B have a known size, either relative to the other or constant? I'd express this as O(A*B), unless you can safely assume that A and B are similar in size (and can both be called "n"). – Samwise Mar 27 '21 at 15:12
  • `O(N * M)` -- same as the equivalent nested loop (`N` is the linear size of A, `M` is the linear size of B) -- listcomps are ever so slightly faster than normal loops in python because of bytecode overhead, but they are not algorithmically so – anthony sottile Mar 27 '21 at 15:14
  • @Samwise Both have known size. You can assume that the length of A and B is exact same. – satta sunder talukder Mar 27 '21 at 15:15
  • @AnthonySottile Thank you. That was exactly my point. If they have any algorithmic significant. It's clear now. – satta sunder talukder Mar 27 '21 at 15:18

1 Answers1

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

miquelvir
  • 1,748
  • 1
  • 7
  • 21