# Why is the worst case for this function O(n^2)?

I'm trying to teach myself how to calculate BigO notation for an arbitrary function. I found this function in a textbook. The book asserts that the function is O(n2). It gives an explanation as to why this is, but I'm struggling to follow. I wonder if someone might be able to show me the math behind why this is so. Fundamentally, I understand that it is something less than O(n3), but I couldn't independently land on O(n2)

Suppose we are given three sequences of numbers, A, B, and C. We will assume that no individual sequence contains duplicate values, but that there may be some numbers that are in two or three of the sequences. The three-way set disjointness problem is to determine if the intersection of the three sequences is empty, namely, that there is no element x such that x ∈ A, x ∈ B, and x ∈ C.

Incidentally, this is not a homework problem for me -- that ship has sailed years ago : ), just me trying to get smarter.

``````def disjoint(A, B, C):
"""Return True if there is no element common to all three lists."""
for a in A:
for b in B:
if a == b: # only check C if we found match from A and B
for c in C:
if a == c # (and thus a == b == c)
return False # we found a common value
return True # if we reach this, sets are disjoint
``````

 According to the textbook:

In the improved version, it is not simply that we save time if we get lucky. We claim that the worst-case running time for disjoint is O(n2).

The book's explanation, which I struggle to follow, is this:

To account for the overall running time, we examine the time spent executing each line of code. The management of the for loop over A requires O(n) time. The management of the for loop over B accounts for a total of O(n2) time, since that loop is executed n different times. The test a == b is evaluated O(n2) times. The rest of the time spent depends upon how many matching (a,b) pairs exist. As we have noted, there are at most n such pairs, and so the management of the loop over C, and the commands within the body of that loop, use at most O(n2) time. The total time spent is O(n2).

(And to give proper credit ...) The book is: Data Structures and Algorithms in Python by Michael T. Goodrich et. all, Wiley Publishing, pg. 135

 A justification; Below is the code before optimization:

``````def disjoint1(A, B, C):
"""Return True if there is no element common to all three lists."""
for a in A:
for b in B:
for c in C:
if a == b == c:
return False # we found a common value
return True # if we reach this, sets are disjoint
``````

In the above, you can clearly see that this is O(n3), because each loop must run to its fullest. The book would assert that in the simplified example (given first), the third loop is only a complexity of O(n2), so the complexity equation goes as k + O(n2) + O(n2) which ultimately yields O(n2).

While I cannot prove this is the case (thus the question), the reader can agree that the complexity of the simplified algorithm is at least less than the original.

 And to prove that the simplified version is quadratic:

``````if __name__ == '__main__':
for c in [100, 200, 300, 400, 500]:
l1, l2, l3 = get_random(c), get_random(c), get_random(c)
start = time.time()
disjoint1(l1, l2, l3)
print(time.time() - start)
start = time.time()
disjoint2(l1, l2, l3)
print(time.time() - start)
``````

Yields:

``````0.02684807777404785
0.00019478797912597656
0.19134306907653809
0.0007600784301757812
0.6405444145202637
0.0018095970153808594
1.4873297214508057
0.003167390823364258
2.953308343887329
0.004908084869384766
``````

Since the second difference is equal, the simplified function is indeed quadratic:

 And yet even further proof:

If I assume worst case (A = B != C),

``````if __name__ == '__main__':
for c in [10, 20, 30, 40, 50]:
l1, l2, l3 = range(0, c), range(0,c), range(5*c, 6*c)
its1 = disjoint1(l1, l2, l3)
its2 = disjoint2(l1, l2, l3)
print(f"iterations1 = {its1}")
print(f"iterations2 = {its2}")
disjoint2(l1, l2, l3)
``````

yields:

``````iterations1 = 1000
iterations2 = 100
iterations1 = 8000
iterations2 = 400
iterations1 = 27000
iterations2 = 900
iterations1 = 64000
iterations2 = 1600
iterations1 = 125000
iterations2 = 2500
``````

Using the second difference test, the worst case result is exactly quadratic.

• Either the book is wrong or your transcription is. Sep 8 '19 at 3:39
• Nope. Wrong is wrong regardless of how well cited. Either explain why we can't simply assume these if's go the worst way they can when doing big O analysis or accept the results you're getting. Sep 8 '19 at 3:51
• @candied_orange; I've added some further justification to the best of my ability - not my strong suit. I would ask that you again allow for the possibility that you might indeed be incorrect. You have made your point, duly taken. Sep 8 '19 at 4:00
• Random numbers aren’t your worst case. That proves nothing. Sep 8 '19 at 4:28
• ahh. okay. The "no sequence has duplicate values" does change the worst case since C can only trigger once per any A. Sorry about the frustration - that's what I get for being on stackexchange late on a Saturday :D Sep 8 '19 at 5:35

The book is indeed correct, and it provides a good argument. Note that timings are not a reliable indicator of algorithmic complexity. The timings might only consider a special data distribution, or the test cases might be too small: algorithmic complexity only describes how resource usage or runtime scales beyond some suitably large input size.

The book makes the argument that complexity is O(n²) because the `if a == b` branch is entered at most n times. This is non-obvious because the loops are still written as nested. It is more obvious if we extract it:

``````def disjoint(A, B, C):
AB = (a
for a in A
for b in B
if a == b)
ABC = (a
for a in AB
for c in C
if a == c)
for a in ABC:
return False
return True
``````

This variant uses generators to represent intermediate results.

• In the generator `AB`, we will have at most n elements (because of the guarantee that input lists won't contain duplicates), and producing the generator takes O(n²) complexity.
• Producing the generator `ABC` involves a loop over the generator `AB` of length n and over `C` of length n, so that its algorithmic complexity is O(n²) as well.
• These operations are not nested but happen independently, so that the total complexity is O(n² + n²) = O(n²).

Because pairs of input lists can be checked sequentially, it follows that determining whether any number of lists are disjoint can be done in O(n²) time.

This analysis is imprecise because it assumes that all lists have the same length. We can say more precisely that `AB` has at most length min(|A|, |B|) and producing it has complexity O(|A|•|B|). Producing `ABC` has complexity O(min(|A|, |B|)•|C|). Total complexity then depends how the input lists are ordered. With |A| ≤ |B| ≤ |C| we get total worst-case complexity of O(|A|•|C|).

Note that efficiency wins are possible if the input containers allow for fast membership tests rather than having to iterate over all elements. This could be the case when they are sorted so that a binary search can be done, or when they are hash sets. Without explicit nested loops, this would look like:

``````for a in A:
if a in B:  # might implicitly loop
if a in C:  # might implicitly loop
return False
return True
``````

or in the generator-based version:

``````AB = (a for a in A if a in B)
ABC = (a for a in AB if a in C)
for a in ABC:
return False
return True
``````
• This would be so much clearer if we just abolished this magical `n` variable, and talked about the actual variables at play. Sep 8 '19 at 18:58
• @code_dredd No it's not, it has no direct connection to the code. It's an abstraction that envisions that `len(a) == len(b) == len(c)`, which although true in the context of time complexity analysis, tends to confuse the conversation. Sep 9 '19 at 0:14
• @SteveJ Timing can help verify the complexity, but not only is good timing very tricky, it also runs into problems with the definition of Big-O notation. Let T(n) be the runtime and f(n) some complexity class. Then T(n) is in O(f(n)) if there exists some minimal input size n0 and some constant factor k, so that for every input n ≥ n0: T(n) ≤ k f(n). So the complexity class only describes growth at suitably large input sizes. We do not know up front what that minimum size n0 is. Below this size, other effects can dominate. This also means: best complexity doesn't imply best performance.
– amon
Sep 9 '19 at 5:42
• Perhaps saying that OP's code has worst case complexity O(|A|•|B| + min(|A|, |B|)•|C|) is enough to trigger understanding? Sep 9 '19 at 11:23
• "Note that timings are not a useful indicator of algorithmic complexity. " I think this would be more accurate if it said "rigorous" or "reliable" rather than "useful". Sep 9 '19 at 18:44

Note that if all elements are different in each of the list which is assumed, you can iterate C only once for each element in A (if there's element in B which is equal). So inner loop is O(n^2) total

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
``````

If the inputs of this function are considered to be three arbitrary collections, the above code is O(n³).

But, as mentioned by @sdenham :

by stipulation, it is being analyzed as a function from three sets to a boolean, which is O(n²) for a non-obvious (and therefore pedagogically useful) reason.

As explained by other answers, if no duplicates are allowed, the worst-case is indeed O(n²).

An additional 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.

• Your last comment is quite interesting, hadn't thought of that. Are you suggesting that is due to your being able to do three O(n) operations in series? Sep 9 '19 at 2:44
• Unless you get a perfect hash with at least one bucket per input element you cannot test inclusion in O(1). A sorted set usually has O(log n) lookup. Unless you are talking about average cost, but that's not what the question is about. Still, having a balanced binary set getting hard O(n log n) is trivial. Sep 9 '19 at 2:50
• @JanDorniak I think sets and dicts are hash tables in python as opposed to the red-black trees in C++. So the absolute worst case is worse, up to 0(n) for a search, but the average case is O(1). As opposed to O(log n) for C++ wiki.python.org/moin/TimeComplexity. Given that it's a python question, and that the domain of the problem leads to a high likelyhood of average case performance, I don't think the O(1) claim is a poor one. Sep 9 '19 at 14:18
• I think I see the issue here: when the authors say "we will assume that no individual sequence contains duplicate values", that is not a step in answering the question; it is, rather, a precondition under which the question is going to be addressed. For pedagogical purposes, this turns an uninteresting problem into one that challenges peoples' intuitions about big-O - and it seems to have been successful at that, judging by the number of people who have strongly insisted that O(n²) must be wrong... Also, while it is moot here, counting the number of steps in one example is not an explanation. Sep 9 '19 at 17:22
• @EricDuminil This code, if considered as a function from three arbitrary collections to a boolean, is O(n³). However, by stipulation, it is being analyzed as a function from three sets to a boolean, which is O(n²) for a non-obvious (and therefore pedagogically useful) reason. In situations where it is being used as the latter, it would be pointless to analyze it as the former. If it were written in a more strongly-typed language, it might not even be possible to create a program in which it is applied to arbitrary collections... Oct 2 '21 at 12:59

To put things into the terms that your book uses:

I think you have no problem understanding that the check for `a == b` is worst-case O(n2).

Now in the worst case for the third loop, every `a` in `A` has a match in `B`, so the third loop will be called every time. In the case where `a` doesn't exist in `C`, it will run through the entire `C` set.

In other words, it's 1 time for every `a` and 1 time for every `c`, or n * n. O(n2)

So there is the O(n2) + O(n2) that your book points out.

The trick of the optimized method is to cut corners. Only if a and b match, c will be given worth a look. Now you may figure that in the worst case you would still have to evaluate each c. This is not true.

You probably think the worst case is that every check for a == b results in a run over C because every check for a == b returns a match. But this is not possible because the conditions for this are contradictory. For this to work you would need an A and a B that contain the same values. They may be ordered differently but each value in A would have to have a matching value in B.

Now here's the kicker. There is no way to organize these values so that for each a you would have to evaluate all b's before you find your match.

``````A: 1 2 3 4 5
B: 1 2 3 4 5
``````

This would be done instantly because the matching 1's are the first element in both series. What about

``````A: 1 2 3 4 5
B: 5 4 3 2 1
``````

That would work for the first run over A: only the last element in B would yield a hit. But the next iteration over A would already have to be quicker because the last spot in B is already occupied by 1. And indeed this would take only four iterations this time. And this gets a little better with every next iteration.

Now I am no mathematician so I cannot proof this will end up in O(n2) but I can feel it on my clogs.

• The order of the elements does not play a role here. The significant requirement is that there are no duplicates; the argument then is that the loops can be transformed into two separate `O(n^2)` loops; which gives overall `O(n^2)` (constants are ignored).
– AnoE
Sep 9 '19 at 12:04
• @AnoE Indeed, the order of the elements does not matter. Which is exactly what I am demonstrating. Sep 9 '19 at 12:58
• I see what you are trying to do, and what you are writing is not wrong, but from the perspective of OP, your answer is mainly showing why a particular train of thought is irrelevant; it is not explaining how to arrive at the actual solution. OP does not seem to give an indication that he actually thinks this is related to order. So it is unclear to me how this answer would help OP.
– AnoE
Sep 9 '19 at 13:51

Note that the algorithm given is unnecessary complicated. An obvious O(n^2) algorithm that is also O(n^2) for arrays with duplicated elements is very simple:

1. Write a function contains(array A, value X) which returns whether A contains X in O(n); this is trivial.

2. Disjoint(array A, B, C): for a in A: if contains(B, a) and contains (C, a) return false. Finally return true. Obviously O(n^2).

If your standard library implements sets then likely as a hash table checking membership in O(log n), so the total would be O(n log n). And if A, B and C are all sorted arrays then you can check if they are disjoint in O(n).

To make the algorithm a bit faster, pay some attention to the size of the sets or arrays. For unsourced arrays, pick A as the array with the smallest number of elements, and B with the second smallest number. This makes the worst case better. But also this will exclude the most searches. The number of common elements will be smallest between the two smallest sets.

The effect is stronger for sets with O(log n) lookup. The number of lookups grows linear with the size of A, the time for each lookup only logarithmic with the size of B or C, so you really want A to be the smallest set.

Was baffled at first, but Amon's answer is really helpful. I want to see if I can do a really concise version:

For a given value of `a` in `A`, the function compares `a` with every possible `b` in `B`, and it does it only once. So for a given `a` it performs `a == b` exactly `n` times.

`B` doesn't contain any duplicates (none of the lists do), so for a given `a` there will be at most one match. (That's the key). Where there is a match, `a` will be compared against every possible `c`, which means that `a == c` is carried out exactly n times. Where's there is no match, `a == c` doesn't happen at all.

So for a given `a`, there are either `n` comparisons, or `2n` comparisons. This happens for every `a`, so the best possible case is (n²) and the worst is (2n²).

TLDR: every value of `a` is compared against every value of `b` and against every value of `c`, but not against every combination of `b` and `c`. The two issues add together, but they don't multiply.

Think about it this way, some numbers may be in two or three of the sequences but the average case of this is that for each element in set A, an exhaustive search is performed in b. It is guaranteed that every element in set A will be iterated over but implied that less than half of the elements in set b will be iterated over.

When the elements in set b are iterated over, an iteration happens if there's a match. this means that the average case for this disjoint function is O(n2) but the absolute worst case for it could be O(n3). If the book didn't go into detail, it would probably give you average case as an answer.

• The book is quite clear that O(n2) is the worst case, not the average case. Sep 8 '19 at 3:32
• A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function. Associated with big O notation are several related notations, using the symbols o, Ω, ω, and Θ, to describe other kinds of bounds on asymptotic growth rates. Wikipedia - Big O Sep 8 '19 at 4:50
• "If the book didn't go into detail, it would probably give you average case as an answer." – Uhm, no. Without any explicit qualification, we are usually talking about worst-case step complexity in the RAM model. When talking about operations on data structures, and it is clear from the context, then we might be talking about amortized worst-case step complexity in the RAM model. Without explicit qualification, we will generally not talk about best case, average case, expected case, time complexity, or any other model except RAM. Sep 8 '19 at 6:07