Run Time for Linear Probing on Hash table

Question

Hello,

what is the running time (big Oh) for linear probing on insertion, deletion and searching.

Thanks

Answer 1

Theoretical worst case is O(n) since if you happen to insert all the elements such that they consecutively collide then the last element inserted will have to be put into the table n steps from its original hash position.

You could however calculate the average expected number of steps if you know the distribution of your input elements (possibly assuming random, but of course assumption is the mother...), know the distribution of your hashing function (hopefully uniform, but it depends on the quality of your algorithm), the length of your hash table and the number of elements inserted.

If your hashing function is sufficiently uniform you can calculate the probability of collisions using the birthday problem and from those probabilities calculate expected probing lengths.