NH> It seems to me that the ideal would be some sort of a hash
NH> involving  a second array, as long in bits as there are integer
NH> numbers. Each  integer would set a bit.  If that bit had been
NH> previously set, bingo,  a duplicate.

PS>You know, for our good old 32 bit unsigned int, you'd need 
PS>4G bits, meaning 512 MB for the hash table alone. On a real 
PS>system, this would seriously trash the data cache in the 
PS>CPU.

I don't know of a 32-bit real system.  By "real" I take it that you mean 
a system using segments and offsets.  I'll bet the paging system in 
memory looks forward to flexing its muscles with that.  Whatever, I 
think that it's time I try it out for myself.

NH> It seems to me as though the big-O for that function is 1.  Is
NH> that  correct?

PS>Lookup in the hash would be O(1) for one number, but you'd 
PS>need to run through all the numbers in your original array, 
PS>so O(n).

Oops, you're right.

PS>The most primitive algorithm for this problem 
PS>(compare each with each) would be O(n^2).

Yipes, I hope it doesn't come to that.

þ CMPQwk 1.42 999

--- Maximus/2 3.01