In mathematical set theory, two sets are considered "disjoint" if they have no elements in common. The following C++ function tests whether two instances of std::set are disjoint. It returns true if the two sets, a and b, are disjoint (they have no elements in common) or false if the two sets are not disjoint (they have at least one element in common).
Checks if two sets, a and b, are disjoint. // a and b are disjoint if and only if they have no elements in common. template bool areDisjoint(std::set& a, std::set& b) { // Iterate through the items in a. for (const T& item : a) { // b. find() == b. end() if and only if the item isn't in b. if (b. find(item) != b. end()) { // If the b contains the current item being checked, then it's in both sets. // Return false (sets aren't disjoint). return false; } } // If no item was in both sets, then return true (the sets are disjoint). return true; }
a. Describe the best case scenario for areDisjoint. Under what conditions will the function return most quickly?
b. Describe the worst case scenario for areDisjoint. Under what conditions will the function take the most time to return?
c. What is the best-case time complexity for areDisjoint in Big-O notation? Use m and n in your answer, as defined above, and explain the reasoning behind your answer.
d. What is the worst-case time complexity for areDisjoint in Big-O notation? Usem and n in your answer, as defined above, and explain the reasoning behind your answer.
e. It will often be the case that set "a" is larger than set "b." How could you modify the implementation of areDisjoint() to improve the worst-case time complexity in this scenario?