Can you use some sort of hash table to store all elements of the first
list, then check whether it contains each element of the second ? This
might be O(n) in most cases.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google
Thanks for your reply. These two lists keep changing on every
iteration(every iteration gives a new sorted list),I have to find the
common elements in two frest lists on every iteration. So if I create a
hash table for one of the lists, then the hash table itself would have
to be recreated
Amith,
I did think of the summation that you mentioned, however it would take
O(n) time to sum up the elements and a further O(n) to do the
checking(the summed elements are not sorted) so it would totally take
about O(n^2) which is not desirable.
Your replies indicate a misunderstanding of asymptotic notation. If
you do several things in a row, to get the asymptotic performance, you
take the worst performer's speed and use that.
For instance, with the hash, you do several things in a row :
Create the hash: O(n)
Fill the hash: O(n)
However I have another problem, there may be 1 to 5 such
coordinates in each list. will the has table become unweildy in such a
case?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
