Hi Neil.

17-May-04 22:41:00, Neil Heller wrote to All


 NH> The question:

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

the best approach would probably be to qsort or radix-sort the array
and then parse it for repeated values.

 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.

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

 O(hash-table-size) + O(n)

the hash-table-size could be the determining factor... note: many compilers
won't let you make an array big enough to have one cell for each integer
value, so you'll be playing with bitmaps

this algorithmwill slow where physical memory is limited
and also with small input data sets.

if you sort the array and then parse it for dupes
you can do that in O(n) time using a radix sort.
and using  hopefully mucn less memory (need space for 4 times the size of
the array)

qsort O(n.log(n)) could be faster than raiix sort for small arrays.

 -=> Bye <=-

---