Created
November 27, 2013 05:39
-
-
Save t33chong/7671155 to your computer and use it in GitHub Desktop.
My textbook claims the worst case runtime of this function is O(n^2). I don't understand why - there are 3 nested loops, shouldn't it be O(n^3)?
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def disjoint2(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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
From the textbook (Goodrich's Data Structures & Algorithms in Python): "We claim that the worst-case running time for disjoint2 is O(n^2). There are quadratically many pairs (a,b) to consider. However, if A and B are each sets of distinct elements, there can be at most O(n) such pairs with a equal to b. Therefore, the innermost loop, over C, executes at most n times."