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 I /Returns true if there is no element common to all three arrays. 2 public static boolean disjointlint groupA, int groupB, int groupC) 3 for (int a groupA) for (int b groupB) for (int c groupC) 6 if ((a-b) && (b-c)) // we found a common value // if we reach this, sets are disjoint return false 8 return true; Algorithm disjoint1 for testing three-way set disjointness. 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: I/Returns true if there is no element common to all three arrays. 2 public static boolean disjoint2(int] groupA, groupB, int groupC) 3 for (int a : groupA) 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; 1O Algorithm disjoint2 for testing three-way set disjointness. Calculate the worst-case running time in asymptotic notation. . Mention the improvements, if any

Explanation / Answer

1) the worst case copmlexity for this senario is O(N^3). assume the each set of size is n.

1) fror the second question the worst case copmlexity for this senario is also O(N^3). assume the each set of size is n.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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