Finding intersection of two arrays

[legend986]

I came across this question of finding the intersection of two unsorted arrays in the shortest time. I had two ideas, one was a brute force - this does it in O(n^2) if I'm not mistaken. The other was to create a has table of the smaller array and then use the second array to map into the hash to determine if the key exists. I want to find out the complexity of this method. Can someone please help me out?

First array: Size of m
Second Array: Size of n

I saw the answer was something like O(mlogm + nlogn) + O(m+n) but I want to know how it is derived.

Also, are there any other methods to find this out?

[JimK]

I saw the answer was something like O(mlogm + nlogn) + O(m+n) but I want to know how it is derived.

O(mlogm + nlogn): is the time you need to sort both arrays
O(m+n): is the time you need to search

BUT I think that using Hash Table you don`t have to sort the arrays. So you can avoid the factor O(mlogm + nlogn).
You can just (using Hash table) store the first array in time O(m) and O(n) to check the contents of the second.
Unfortunately this has good time complexity but it hasn`t good space complexity!!!

[legend986]

Thanks I wonder why it has a bad space complexity... Is it because the numbers could be over any range?

[JimK]

OK, when you try to find the complexity [time or space] of an algorithm, you try to find what happens when the input is very big...