2 added 275 characters in body
source | link

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
source | link

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