You are given two sets of n numbers A = { a 1, ..., a n } and B = { b 1, ..., b

ID: 3837036 • Letter: Y

Question

You are given two sets of n numbers A = {a1, ..., an} and B = {b1, ..., bn}. These sets are not sorted. Since A and B are sets, they do not contain duplicates (i.e., there are no indices i and j such that ai = aj or bi = bj).

Consider each of the following algorithms for computing the intersection of the two sets A B. For each algorithm, state and briefly justify the asymptotic running time of the algorithm. (State your running times in terms of n.) Then, describe one disadvantage of the algorithm.

Algorithm #1: Put A and B together in one array and sort the array. Scan through the sorted array and look for numbers that are repeated. The repeated numbers belong in A B.

Algorithm #2: Put the items from A in a red-black tree. Then for each bi in B, look for bi in this red-black tree. If found, bi belongs in the intersection A B.

Algorithm #3: Put the items from A in a hash table. Then, for each bi in B, look for bi in this hash table. If found, bi belongs in the intersection A B.

Explanation / Answer

Algorithm #1: Put A and B together in one array and sort the array. Scan through the sorted array and look for numbers that are repeated. The repeated numbers belong in A B.

Put A and B together in one array and sort the array. : Takes O(2nlog2N)
Scan through the sorted array and look for numbers that are repeated. : Takes O(N2)
Overall time coimplexity is O(N2)

Algorithm #2: Put the items from A in a red-black tree. Then for each bi in B, look for bi in this red-black tree. If found, bi belongs in the intersection A B.

Put the items from A in a red-black tree. : N items and each taken Log n, So overall it takes O(NlogN)
Then for each bi in B, look for bi in this red-black tree. If found, bi belongs in the intersection A B. Takes O(NlogN)
Because to seach one element in R-B tree it takes log n, for n elements it takes nlogn
Overall time coimplexity is O(NlogN)

Algorithm #3: Put the items from A in a hash table. Then, for each bi in B, look for bi in this hash table. If found, bi belongs in the intersection A B.

Put the items from A in a hash table. : Takes O(n) time and O(n) space
Then, for each bi in B, look for bi in this hash table. If found, bi belongs in the intersection A B. : Since searching is O(1) in hash, So time taken will be O(n)
Overall time coimplexity is O(N)

Navigate

You are given two sequences, (a_1, a_2, ..., a_n) and (b_1, b_2, ..., b_n), wher

You are given two sets of thin samples in which one set is very hydrophobic and

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

You are given two sets of n numbers A = { a 1, ..., a n } and B = { b 1, ..., b

Question

Explanation / Answer

Related Questions

Navigate