Question

The following algorithm takes as input an array, and returns the array with all the duplicate...

The following algorithm takes as input an array, and returns the array with all the duplicate elements removed. For example, if the input array is {77, 78, 78, 64, 39, 78, 39}, the algorithm returns {77, 78, 64, 39}.


S = new empty set
D = new empty dynamic array
for every element x in input array
if not S.member(x) then
S.insert(x)
D.append(x)
return D

What is the big-O complexity of this algorithm, if the set is implemented as
a) A hash table?
b) A Balanced BST .Give reasons.

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

a)For hash table in worst case it takes 0(n) time

When there are collisions and to resolve them if we use linked list method(chaining) we have to search till end of the list to know if the new element is duplicate or not

If there are no collisions time taken is o(1)

b)for balanced BST worst case is 0(height of the tree).

when a new element is being inserted we may traverse till the leaves of the tree in worst case

height of bst is o(log n).

Therefore for finding whether the new element being inserted is duplicate time taken is o(log n)

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm...
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm that is executed most frequently. Express the number of times it is executed as a function of N. Convert this expression into the Big-O notation. A. For each of the three fragments of code, what is its worst-case time complexity, in the form "O(…)". (Use the given solution to the first problem as a model)                 //----------------- This is a sample problem – solved ------...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number in A and an O(log n)-time computation for each odd number in A. What is the best-case running time of Algorithm X? What is the worst-case running time of Algorithm X? 2. Given an array, A, of n integers, give an O(n)-time algorithm that finds the longest subarray of A such that all the numbers in that subarray are in sorted order. Your algorithm...
How to use C++ figure this question? Collection and Sorted Collection An array is great for...
How to use C++ figure this question? Collection and Sorted Collection An array is great for storing a list of values. However, one challenge when working with arrays is they have a fixed size. If you declare an array of size 10 and later need to actually store 11 elements you have to create a new array and copy everything over. C++ (and other langauges) create classes that handle this and other operations behind the scenes. In this assignment, we...
Problem Definition: Problem: Given an array of integers find all pairs of integers, a and b,...
Problem Definition: Problem: Given an array of integers find all pairs of integers, a and b, where a – b is equal to a given number. For example, consider the following array and suppose we want to find all pairs of integers a and b where a – b = 3 A = [10, 4, 6, 16, 1, 6, 12, 13] Then your method should return the following pairs: 4, 1 15, 12 13, 10 A poor solution: There are...
import java.util.ArrayList; /* Rules:         1. Allow Tester to iterate through all nodes using the...
import java.util.ArrayList; /* Rules:         1. Allow Tester to iterate through all nodes using the in-order traversal as the default.             This means, in Tester the following code should work for an instance of this class             called bst that is storing Student objects for the data:                 BinarySearchTree_Lab08<String> bst = new BinarySearchTree_Lab08<String>();                 bst.add("Man");       bst.add("Soda");   bst.add("Flag");                 bst.add("Home");   bst.add("Today");   bst.add("Jack");                ...
Using the following code perform ALL of the tasks below in C++: ------------------------------------------------------------------------------------------------------------------------------------------- Implementation: Overload input...
Using the following code perform ALL of the tasks below in C++: ------------------------------------------------------------------------------------------------------------------------------------------- Implementation: Overload input operator>> a bigint in the following manner: Read in any number of digits [0-9] until a semi colon ";" is encountered. The number may span over multiple lines. You can assume the input is valid. Overload the operator+ so that it adds two bigint together. Overload the subscript operator[]. It should return the i-th digit, where i is the 10^i position. So the first...
Please ask the user to input a low range and a high range and then print...
Please ask the user to input a low range and a high range and then print the range between them. Add printRang method to BST.java that, given a low key value, and high key value, print all records in a sorted order whose values fall between the two given keys from the inventory.txt file. (Both low key and high key do not have to be a key on the list). ****Please seperate the information in text file by product id,...
For a C program hangman game: Create the function int setup_game [int setup_game ( Game *g,...
For a C program hangman game: Create the function int setup_game [int setup_game ( Game *g, char wordlist[][MAX_WORD_LENGTH], int numwords)] for a C program hangman game. (The existing code for other functions and the program is below, along with what the function needs to do) What int setup_game needs to do setup_game() does exactly what the name suggests. It sets up a new game of hangman. This means that it picks a random word from the supplied wordlist array and...
Assignment 1 - ITSC 2214 I have to complete the array list for a shopping list...
Assignment 1 - ITSC 2214 I have to complete the array list for a shopping list code and can't figure out how to complete it: Below is the code Complete the three empty methods (remove(), find(), and contains()) in the ShoppingListArrayList.java file. These methods are already implemented in the ShoppingListArray class. /////////////////////////////////////////////////////////////////////////////////////////////////////////// Grocery Class (If this helps) package Shopping; public class Grocery implements Comparable<Grocery> { private String name; private String category; private int aisle; private float price; private int quantity;...
This laboratory assignment involves implementing a data structure called a map. A map associates objects called...
This laboratory assignment involves implementing a data structure called a map. A map associates objects called keys with other objects called values. It is implemented as a Java class that uses arrays internally. 1. Theory. A map is a set of key-value pairs. Each key is said to be associated with its corresponding value, so there is at most one pair in the set with a given key. You can perform the following operations on maps. You can test if...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT