Complexity Analysis
def has_common(a, b):
for x in a:
if x in b:
return True
return FalseWhat is the time and space complexity?
Work it out before scrolling down.
Time
O(a × b)
Space
O(1)
How to derive it
Trap: `x in b` on a list is O(b), not O(1). The outer loop runs up to a times, each doing an O(b) scan → O(a × b) worst case. Converting b to a set first would make lookup O(1), reducing total to O(a + b). Always check whether `in` operates on a list or a set/dict.