Like Tree1Likes
  • 1 Post By Malcolm McLean

Intersection of two arrays in O(n) complexity

This is a discussion on Intersection of two arrays in O(n) complexity within the C Programming forums, part of the General Programming Boards category; The question is to find the common elements in two arrays .The code which i wrote have the complexity of ...

  1. #1
    Registered User
    Join Date
    Dec 2012
    Posts
    5

    Intersection of two arrays in O(n) complexity

    The question is to find the common elements in two arrays .The code which i wrote have the complexity of order n square.
    Code:
    void main ()
    { int i,j;
    int a[]={1,2,3,4};
    int b[]={4,5,7,1};
    for (i=0;i<4;i++)
    {
     for (j=0;j<4;j++)
               { if (a[i]==b[j])
                             { 
                                printf("%d",a[i]);
                                          }
                 }
    }
    
    
    }
    How it can be done in linear time

  2. #2
    Registered User
    Join Date
    May 2009
    Posts
    2,541
    Quote Originally Posted by malwaregeek View Post
    The question is to find the common elements in two arrays .The code which i wrote have the complexity of order n square.


    How it can be done in linear time
    The obvious answer to me is it can be done if the arrays are sorted.

    Tim S.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  3. #3
    Registered User
    Join Date
    Dec 2012
    Posts
    5
    Yes in that case it could be definitely done in linear time. But even in case of unsorted arrays, it could be done ,one of my friend told me to use hashmap, but I have no idea how to implement though I know it theoretically.

  4. #4
    Registered User
    Join Date
    Dec 2012
    Posts
    45
    Quote Originally Posted by malwaregeek View Post
    Yes in that case it could be definitely done in linear time. But even in case of unsorted arrays, it could be done ,one of my friend told me to use hashmap, but I have no idea how to implement though I know it theoretically.
    With a hash map you would get O(n log n) time with O(n) additional memory. Pretty good, but not as O(n) time.

    You can achieve O(n) time if the range of values is reasonably small: You set up an array of bits ---one for each possible value--- set to zero. Then mark with ones the bits of the values present in one array. Then traverse the other array, checking if its values were marked...

  5. #5
    Registered User
    Join Date
    Dec 2012
    Posts
    45
    Oops. Sorry, I was thinking in a traditional [tree] map... With a hash map you can also get O(n) time, but only if you make the hash table reasonably big (proportional to the number of different values) and you avoid storing duplicates separately.

  6. #6
    Registered User
    Join Date
    May 2012
    Posts
    333
    Quote Originally Posted by comocomocomo View Post
    Oops. Sorry, I was thinking in a traditional [tree] map... With a hash map you can also get O(n) time, but only if you make the hash table reasonably big (proportional to the number of different values) and you avoid storing duplicates separately.
    I was going to say. In practice the memory and computational overhead of a hash table is too high, and the way to do it is to sort both arrays. But a hash is an O(N) way of retrieving a database entry by content.
    iMalc likes this.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    http://www.malcolmmclean.site11.com/www

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    I once began writing a modified IntroSelect sort of algorithm that operates on both arrays at once to see if their contents are the same but would allow for early outs that could mean it typically beats the hashing option in practice. Of course it requires that the array ordering need not necessarily be maintained. I never quite got it working properly in all cases and I cant remember where the code went.

    I'd probably just sort both and compare. Radix Sort can be used to turn it into linear time, but if I was that intent on having it linear time then I'd probably just use a hash table.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Intersection of two arrays
    By jacob_76505 in forum C Programming
    Replies: 3
    Last Post: 10-17-2011, 11:45 PM
  2. Intersection of 2 Arrays.
    By lexy in forum C Programming
    Replies: 4
    Last Post: 03-21-2010, 11:21 PM
  3. (C#) Ray->Box intersection
    By Devils Child in forum Game Programming
    Replies: 6
    Last Post: 12-18-2008, 12:02 AM
  4. Intersection between 2 circles
    By darkskylight in forum C++ Programming
    Replies: 3
    Last Post: 01-29-2006, 05:24 AM
  5. intersection and union
    By BaAa3 in forum C Programming
    Replies: 2
    Last Post: 02-29-2004, 03:39 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21