Suppose that we have two sets of integers: X = {x1,x2, ,xn) and Y ={y1,y2,?yk}.

Question

Suppose that we have two sets of integers: X = {x1,x2, ,xn) and Y ={y1,y2,?yk}. Since they are sets, there are no duplicates in X or in Y, but some elements may appear in both sets. We consider efficient algorithms to find those in both, i.e, their intersection. S=X intersection Y. a) Describe how to use sorting to efficiently find S. What is the run time (In Big O)? Note that you can do other things besides sorting. but don?t use hashing here. b) Describe how to use hashing to efficiently find S. What is the expected run time (In Big O) for our usual assumptions about hashing? Be sure to specify the size of any hash tables you use, and what type of collision scheme you propose. c) Suppose that n > > k (for example k = log n). Describe how to modify your solutions for a) and b) to work better in this case (or argue that your solution already solves them well).

Explanation / Answer

a) set L # L is set containing result
L = X;
X = sort(X)
for each element in Y:
   check this element in X:
   if it is present in X:
       do not add this number to X
   else:
       add it to L

Time Complexity :
O(n*log k)
// X is sorted we can search an element in it in O(log n) binary search

b) set L # L is set containing result
L = X;
hash_map = {}
for each element in X:
   add element to hash_map
for each element in Y:
   check this element in hash_map:
   if it is present in hash_map:
       do not add this number to L
   else:
       add it to L
       add this number to hash_map
Time Complexity :
O(n+k)

Difference between Time Complexity between (a) and (b)
since for element in Y in case of Algorithm 1 we are looking in X, which is O(1)
in case 2 we are looking in hash_map which is O(1).

c) since n >> k. we should put the elements of Y in hash_map to avoid a very large heap as it can take lot of memory.
also in aglorithm 1 sort set Y as it would be K*log (k). hence require less time.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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