If I have a hash table of 1000 slots, and I have an array of n numbers. I want to check if there are any repeats in the array of n numbers. The best way to do this that I can think of is storing it in the hash table and use a hash function which assumes simple uniform hashing assumption. Then before every insert you just check all elements in the chain. This makes less collisions and makes the average length of a chain $\alpha = \frac{n}{m} = \frac{n}{1000}$.

I am trying to get the expected running time of this, but from what I understand, you are doing an insert operation up to $n$ times. The average running time of a search for a linked list is $\Theta(1+\alpha)$. Doesn't this make the expected running time $O(n+n\alpha) = O(n+\frac{n^2}{1000}) = O(n^2)$? This seems too much. Am I making a mistake here?

  • $\begingroup$ the expected number of collisions is $O(n^2/m)$ which is $O(n)$ for $m = \Omega(n)$. the running time to find duplicates is essentially bounded by the number of collisions $\endgroup$ – Sasho Nikolov Mar 13 '13 at 3:39

Why not sort the array, then iterate over the sorted array, comparing the current number to the previous number.

n*log(n) for the sort, n for the iteration = 2n*log(n)

| cite | improve this answer | |
  • 2
    $\begingroup$ This needs memory $n$. Using memory $2n$ (say), you can reduce the running time to linear. $\endgroup$ – Yuval Filmus Mar 13 '13 at 1:42

Not the answer you're looking for? Browse other questions tagged or ask your own question.