The following algorithm solves this problem:
INPUT: n: number of sets S_{0}, ..., S_{n-1}, where S_{i} is a SUBSET of {0,1,...,n-1}. OUTPUT: True, if there is a pair of the input sets S_{i} and S_{j} that are disjoint (in this case, i and j are printed). False, otherwise. ALGORITHM:
cost of each instruction | # of times instruction will be repeated | |
for each set S_{i}: for each other set S_{j}: disjoint = true for each element k of S_{i}: if k belongs to S_{j}: disjoint = false if disjoint == true print 'Sets ',i,j,' are disjoint' return(true) return(false) |
T(n) will be affected also by how you implement the "for each other set S_{j}" instruction. Note that it is enough to consider j > i only. [Hint: Studying the runtime analysis of InsertionSort in section 2.2 of the textbook will help you think of ideas to express the number of iterations of the instructions in the algorithm above.]
[[2, 3, 0], [4, 2], [1, 4, 3, 0], [2], []]
[[1, 0, 1, 1, 0], [0, 0, 1, 0, 1], [1, 1, 0, 1, 1], [0, 0, 1, 0, 0], [0, 0, 0, 0, 0]]
def DisjointSetsVersion1(L): ... def DisjointSetsVersion2(L): ...
Submit your code on myWPI.
a^{n}Provide a detailed, rigorous proof of each part of your solution.
n^{a}
a^{na}
log_{a}(n)
a^{a*n}
n^{loga(n)}where a is a constant greater than 1.
Transitivity of Big-O: If f(n) = O(g(n)) and g(n) = O(h(n)) then f(n) = O(h(n)).
import sys sys.setrecursionlimit(12000)I include here the skeleton of a Python program that I wrote which satisfies the requirements below.
[n-1, n-2, ..., 2, 1, 0]
Submit your Python program on myWPI.