2 added 275 characters in body edited Sep 8 '19 at 13:52 Eric Duminil 14755 bronze badges We will assume that no individual sequence contains duplicate. is a very important piece of information. Otherwise, the worst-case of optimized version would still be O(n³), when A and B are equal and contain one element duplicated n times: ``````i = 0 def disjoint(A, B, C): global i for a in A: for b in B: if a == b: for c in C: i+=1 print(i) if a == c: return False return True print(disjoint([1] * 10, [1] * 10, [2] * 10)) `````` which outputs: ``````... ... ... 993 994 995 996 997 998 999 1000 True `````` So basically, the authors assume that the O(n³) worst-case shouldn't happen (why?), and "prove" that the worst-case is now O(n²). The real optimization would be to use sets or dicts in order to test inclusion in O(1). In that case, `disjoint` would be O(n) for every input. We will assume that no individual sequence contains duplicate. is a very important piece of information. Otherwise, the worst-case of optimized version would still be O(n³), when A and B are equal and contain one element duplicated n times: ``````i = 0 def disjoint(A, B, C): global i for a in A: for b in B: if a == b: for c in C: i+=1 print(i) if a == c: return False return True print(disjoint([1] * 10, [1] * 10, [2] * 10)) `````` which outputs: ``````... ... ... 993 994 995 996 997 998 999 1000 True `````` We will assume that no individual sequence contains duplicate. is a very important piece of information. Otherwise, the worst-case of optimized version would still be O(n³), when A and B are equal and contain one element duplicated n times: ``````i = 0 def disjoint(A, B, C): global i for a in A: for b in B: if a == b: for c in C: i+=1 print(i) if a == c: return False return True print(disjoint([1] * 10, [1] * 10, [2] * 10)) `````` which outputs: ``````... ... ... 993 994 995 996 997 998 999 1000 True `````` So basically, the authors assume that the O(n³) worst-case shouldn't happen (why?), and "prove" that the worst-case is now O(n²). The real optimization would be to use sets or dicts in order to test inclusion in O(1). In that case, `disjoint` would be O(n) for every input. 1 answered Sep 8 '19 at 12:38 Eric Duminil 14755 bronze badges We will assume that no individual sequence contains duplicate. is a very important piece of information. Otherwise, the worst-case of optimized version would still be O(n³), when A and B are equal and contain one element duplicated n times: ``````i = 0 def disjoint(A, B, C): global i for a in A: for b in B: if a == b: for c in C: i+=1 print(i) if a == c: return False return True print(disjoint([1] * 10, [1] * 10, [2] * 10)) `````` which outputs: ``````... ... ... 993 994 995 996 997 998 999 1000 True ``````