1) Three sets are represented with three integer vectors A, B and C. The followi

Question

1) 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.

1Returns true if there is no element common to all three arrays. 2 public static boolean disjoint1(int ] groupA, int groupB, int] groupC) for (int a groupA) 4 for (int b groupB) for (int c groupC) if ((a-b) && (b-c)) return false; // we found a common value 8 return true; // if we reach this, sets are disjoint Algorithm disjoint1 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 1
• Subjects

---

---

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