Python Time complexity of any and in and for loop

Question

What would be the time complexity (General/Worst case) of the following lines of code?

s1 = "any-string-of-large-size" 
s2 = "anyother-string-of-larger-size"  
if(any(x in s1 for x in s2)):
    return "YES"
return "NO"

This code is for checking if there is any letter common to s1 and s2. I would also like to have any other approach to achieve this which may be more efficient.
I find it difficult to calculate time complexities when using such library functions. Can someone also please explain how to calculate it

To make this faster, you can convert one of the strings to `set` and then test `any(x in set_of_s1 for ...)` or convert both to `set` and get the set intersection. (Actually, in this very specific code, this will be slower, as this `any` return positive for the very first combination of characters, but could be O(n²) in a less-than-optimal case.) — tobias_k, Sep 21 '20 at 15:16
Ohh thanks..thinking in your lines, I think it can be made more faster by using this: `return "YES" if set(s1) & set(s2) else "NO"`. What would be the time complexity in this case ? — Dev5, Sep 21 '20 at 15:19
Exactly. Time complexity would then be O(n) for creating the two sets and the intersection. Using `any` with `in a_set` might be faster (still O(n) though), as this will only have to create one set and then stop early as soon as the first match is found. — tobias_k, Sep 21 '20 at 15:19
So is the time complexity for intersection `&` O(n) or O(1) ? — Dev5, Sep 21 '20 at 15:21
Time complexity for intersection is O(n), since you have to make a O(1) lookup for all the n elements in the set. — tobias_k, Sep 21 '20 at 15:22

score 3 · Accepted Answer · answered Sep 21 '20 at 15:21

3

The best and worst case are O(1) and O(|s1|*|s2|), respectively, where |s1| and |s2| denote the length of the two strings.

Indeed, your code could be rewritten as

for c2 in s2:
   for c1 in s1:
      if c1==c2:
          return "YES"
return "NO"

If you just want to check if the two string share a common char you could write it as

if set(s1) & set(s2):
   return "YES"
return "NO"

This would have the same worst case time complexity O(|s1|*|s2|), but the average case would be O(min(|s1|,|s2|).

answered Sep 21 '20 at 15:21

abc

11,579
2
26
51

It's the worst case considering collisions, unluckily to happen, but still https://wiki.python.org/moin/TimeComplexity – abc Sep 21 '20 at 15:24
Okay, makes sense. Of course, the worst case in the double-loop-scenario is _much_ more likely. – tobias_k Sep 21 '20 at 15:25
@abc Could you please explain what you mean by collisions? – Dev5 Sep 21 '20 at 15:27
1

@Dev5 I think this thread cover your question https://stackoverflow.com/questions/3949310/how-is-set-implemented – abc Sep 21 '20 at 15:32

score 0 · Answer 2 · answered Sep 21 '20 at 15:10

0

The time complexity is O(N) in general for (in) keyword. So x in s2 is straight forward O(N). Which concludes overall complexity to be O(N^2).

answered Sep 21 '20 at 15:10

Dhruv Kothari

103
2
7

Python Time complexity of any and in and for loop

2 Answers2