Explore BrainMass

Running time of a set union implementation

The input consists of two arrays each representing a set of integers (in each array, each value appears only once). The output is an array representing the union of the two sets - again, each value appears only once. Write a method to implement set union and analyze its running time.

Solution Preview

procedure Union

Input: Array set1, Array set2 // Arrays are indexed 0 onwards.
Output: Array set3 // Maximum size of this array is size of set1 + size of set2.

size1 = Number of elements in Array set1
size2 = Number of elements in Array set2
ucount = 0 // To count number of elements in Union Array.

// Check for each element of set1 whether it occurs in set2. If not then copy it to union set3.
for (i=0; i<size1; i++) { // size1 comparisons always.
found = no // size1 assignment operations always.
for (j=0; j<size2; j++) { // size2 comparisons in worst case.

Solution Summary

Solution is presented in pseudo-code form along with plain description for easy understanding. Counts of comparisons as well as assignments are marked for various steps in implementation. Solution analyzes the given implementation for maximum and minimum number of algorithm assignments, worst case algorithm comparisons and maximum number of implementation comparisons.