Three sets are represented with three integer vectors A, B and C. The following

Question

Three sets are represented with three integer vectors A, B and C. The following algorithm calculates three-way set disjointness. In easier terms the problem is to determine if the intersection of the three sets is empty.

observe this code and answer below questions:

-Assume the size of each set to be n.

- Identify the worst-case scenario.

-Calculate the worst-case running time in asymptotic notation.

2) The previous algorithm has been modified to include an improvement: 1* Returns true if there is no element common to all three arrays. 2 public static boolean disjoint2(int ] groupA, int] groupB, int1 groupC) 3 for (int a groupA) 4 for (int b groupB) if (a b) only check C when we find match from A and B for (int c groupC) if (a-c) // and thus b == c as well // we found a common value // if we reach this, sets are disjoint return false; 9 return true; 10 Algorithm disjoint2 for testing three-way set disjointness.

Explanation / Answer

Q. Identify the worst-case scenario.

Ans: If all the elements of A, B, C are different (they are disjoint )

Q. Calculate the worst-case running time in asymptotic notation.

Ans: O(n^3)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.