Hello Neil!

Replying to a message of Neil Heller to All:

 NH> Given an array of integers, write a function to return any duplicated 
 NH> values.  What is the the running time of this algorithm?

I'll leave the writing part as an excersise for the reader.  ;-)

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

That's close.  The problem is that, in reality, you could chew up
significant portions of memory.  So then you end up with some non-perfect
hashing to resolve collisions, blah, blah...

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

No - you still need to go through the list once.  Thus, it's O(n).  That's
the best you can do because it's the minimum required simply to go through
the list.

O(1) would describe the amount of time required to process each member of
the original array.

Darin

---