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 agorithm calculates three-way set disjointness. In easier terms the problem is to determine if the intersection of three sets is empty.

- Assume the size of each set to be n.

-Identify the worst-case scenario.

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

1/** Returns 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 3 for (int a groupA) for (int b : groupB) for (int c groupC) 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.

Explanation / Answer

Worst Case scenario

There are two possible cases

i) Finding a common element which is present as the last element in all three arrays

ii) Finding no common element

For both cases we have to traverse completely all three arrays.

Running Time

for ( int a : groupA ) ----> 2nd outer for loop

for ( int b : groupB ) ----> outer for loop

for ( int c : groupC ) ----> inner for loop

2nd outer for loop executes n times. For every time the 2nd outer for loop executes, the outer for loop executes n times.

=> statements in outer for loop executes n * n times.

For every time the outer for loop executes, the inner for loop executes n times. This means for every time the 2nd outer for loop executes, inner for loop executes n*n times.

=> statements in inner for loop executes n * n* n times.

The time complexitiy is O(n*n*n) => O(n3)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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