Purchase Solution

Running time of a set union implementation

Not what you're looking for?

Ask Custom Question

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.

Purchase this Solution
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.

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.
...

Purchase this Solution
Free BrainMass Quizzes
Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

Probability Quiz

Some questions on probability

Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

View More Free Quizzes
Related BrainMass Solutions

  • Marketing Questions

    They are tools that keep the machine running and running efficiently. When metrics are left out of the process, the chances of a successful implementation are minimal.

  • FMC: Will work groups and teams work at Green River?

    There is possibility of a limited implementation of organizational change in certain sections of the plant.

  • Computing Running Time of a Pseudo Code

    So the running time complexity is O(n). Please note, this is an implementation independent of finding out run time.

  • universal set

    The union of two sets combines the elements of the two sets together. Formally, the union of the sets A and B is defined as the set of all objects, that belong to A or belong to B (or, belong to A and B at the same time).

  • Employee Compensation and Employee Right Issues

    The union, a company reprehensive, and the NRLB fix an election date, time, and place. The workers decide if they want the union to begin negotiations with the company.

  • Kenneth Dailey of FMC Green River: groups, teams, leadership and skills...

    Finally, the question does not mention if implementation of the Aberdeen model would go against the quality control standards set up for the factory.

  • Communication Plan: Key Points for Key Stakeholder Group

    contract, a 2%, 3% and 4% raise over the next three years for all workers, no layoffs, no pension freezes, no paying for our union negotiated healthcare and same high quality employee evaluation tools as are currently set in place.

  • Lean supply chain implementation and risks

    For example, if the regular vendors do not supply goods on time, the backup plan can allow the organization to shift to other vendors of the organization. The solution discusses implementation of lean supply chain and hedging of risks.

  • Disaster Recovery Plan - Project Manager

    As an appointed Project Manager in charge of security setup and operation of a 12-story government credit union and office complex unit; there a several elements of concern that need to be taken into consideration for design and implementation of a successful

View More Related Solutions