Initial algorithm Improved Algorithm The previous aglorithm has been modified to
ID: 3725237 • Letter: I
Question
Initial algorithm
Improved Algorithm
The previous aglorithm has been modified to include an improvement.
- Calculate the worst-case running time in asymptotic notation.
- Mention any improvements, if any.
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
For the initial algorithm, the worst case complexity is O(n3). This is because for each element in groupA, the loop would would run covering all elements in groupB and for each element in groupB, the loop would run for all elements in groupC in the worst case.
For the improved algorithm also the worst case complexity is O(n2) because, for each element in groupA, if there is a matching element in group B then that element in found in O(n) worst case time and for that element again we iterate over groupC that takes O(n) Thus total is O(2n) for each element in groupA. Thus for all elements in groupA, we have worst case complexity = O(2n2).
An improved code is as follows:
public static boolean disjoint2(int ar1[], int ar2[], int ar3[])
{
//first sort the arrays
sort(arr1);
sort(arr2);
sort(arr3);
// Initialize starting indexes for the arrays
int i = 0, j = 0, k = 0;
// Iterate through three arrays while all arrays have elements
while (i < ar1.length && j < ar2.length && k < ar3.length)
{
if (ar1[i] == ar2[j] && ar2[j] == ar3[k])
{ return false; }
// x < y
else if (ar1[i] < ar2[j])
i++;
// y < z
else if (ar2[j] < ar3[k])
j++;
// We reach here when x > y and z < y, i.e., z is smallest
else
k++;
}
return false;
}
The complexity of sorting is O(n1logn1 + n2logn2 + n3logn3 ) and the rest of the process has a complexity of O(n1+n2+n3) . Thus the total compleity is O(nlogn)