[tlug] array duplicate check [C]

["Nguyen Vu Hung" <vuhung16plus@example.com>]

Hi list,

Excuse my elementary question :D

I have two integer arrays  of size N and M and I want to check if none
of the elements in the first arrays are contained in the second array.
The programming language is pure C so no vector or set like Java.

Intuitively, the pseudo code will looks like

for i = 1 to N
for j = 1 to  M
if a[i] in b[j] then fail
end for
end for

whose the complexity is N*M in the worst case. The performance will be
a pain if N or M grow big.

So how can I improve the algorithm? ( for the worst case ) I have a
feeling that I can reduce the complexity to N or M...

Any helps are appreciated.

--
Best Regards,
Nguyen Hung Vu
vuhung16plus{remove}@example.com
VIQR Standard: http://vi.i18n.kde.org/viqr
http://www.flickr.com/photos/vuhung/tags/fav/