Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Computing set intersection in linear time?

Is there an algorithm that, given two sets, computes their intersection in linear time?

I can run two for loops to check all pairs of elements, recording elements that I find in both of the sets. However, the runninng time will be O(n2). How do I do this in O(n) time?

like image 382
NEO Avatar asked Jan 09 '11 22:01

NEO


People also ask

What is the time complexity of set intersection?

What's the time complexity of set intersection in Python? The time complexity of set intersection in Python on a set with n elements and a set argument with m elements is O(min(n, m)) because you need to check for the smaller set whether each of its elements is a member of the larger set.

How do you find the intersecting set?

The intersection of two or more given sets is the set of elements that are common to each of the given sets. The intersection of sets is denoted by the symbol '∩'. In the case of independent events, we generally use the multiplication rule, P(A ∩ B) = P( A )P( B ).

How do you use intersection in sets?

Python Set intersection() Method The intersection() method returns a set that contains the similarity between two or more sets. Meaning: The returned set contains only items that exist in both sets, or in all sets if the comparison is done with more than two sets.


2 Answers

That depends on your set implementation.

If you have a hash set (O(1) lookup), then the approach indicated by all the other posters is correct. Iterate across all the elements in the first set. If it's in the second set, then add it to the result. This runs in O(n) time.

If you have a tree set (O(lg n) lookup), then this approach will work, but it runs in O(n lg n) time. You can do better; there's an O(n) solution. I assume that you have some sort of iterator that can traverse the elements of the two sets in ascending order. If you do, then the question is "given two lists in sorted order, find their intersection." This can be done using a modified version of the algorithm you use to merge two ranges. The idea is to keep track of the two iterators. At each step, compare the first elements of the ranges. If they're equal, add the element to the intersection and advance both iterators forward. If the first is less than the second, then advance the first iterator. If the first element is greater, then advance the second iterator. This runs in time O(n) because each iteration consumes at least one element, and there's only O(n) elements in total.

like image 118
templatetypedef Avatar answered Oct 11 '22 06:10

templatetypedef


I wonder nobody mentioned hashtable.
Regardless of your set implementation (even if 'set' here means a simple array), you can

  1. put contents of the first set into hashtable and
  2. iterate over second set, checking if hashtable contains current element.

O(n)

like image 30
Nikita Rybak Avatar answered Oct 11 '22 06:10

Nikita Rybak