Computing set intersection in linear time?

Asked 2011-01-09T22:11:35.843

46

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(n²). How do I do this in O(n) time?

Edit Report

1 Answer

0

For all elements in set 1: Check if that element is in set 2. You can implement a Set that has amortized O(1) lookup time.

answered 2011-01-09T22:13:47.037

Computing set intersection in linear time?

1 Answer

Your Answer