# How to get expected running time of hash table? [duplicate]

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?

• 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 – Sasho Nikolov Mar 13 '13 at 3:39

• This needs memory $n$. Using memory $2n$ (say), you can reduce the running time to linear. – Yuval Filmus Mar 13 '13 at 1:42