Explore BrainMass

Explore BrainMass

    Running time of a set union implementation

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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.

    © BrainMass Inc. brainmass.com June 3, 2020, 11:43 pm ad1c9bdddf

    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.