Suppose we have a collection of n different subsets of the s

Suppose we have a collection of n different subsets of the set { 1, 2, ..., n } and they are in some arbitrary order, that is, we have subsets S1, S2, ..., Sn, but how many and which elements are in each of these subsets is entirely arbitrary. Suppose also that we have another subset S\' of { 1, 2, ..., n }.

(a) Express a brute-force algorithm that determines whether S\' equal to one of the subsets in the collection.

(b) Give a big-O worst case estimate as a function of n for the time complexity of your algorithm. To receive full credit, you must explain how you obtained your answer.

Solution

So we have subsets S1, S2, ..., Sn and subset S\'.

So first conclusion is worst case of determining whether S\' equal to one of the subsets in the collection, will occur when the length of each of these subsets is maximum. So maximum length of each these subsets is O(n).

Now we have to compare S\' with each of  S1, S2, ..., Sn.

Lets say we compare S\' with S1. Our strategy to find weather S\' is equal to S1 is sort S\' and S1 in O(nlogn) time and compare elements at each index in O(n) time. So this will take O(logn) + O(n) = O(nlogn) time.

So, we will repeat this with all n subsets.

Hence overall time = n*O(nlogn) = O(n^2 * logn)