Runtime for linear probing on a hash table

The theoretical worst case is O (n), because if you have to insert all the elements so that they collide sequentially, then the last inserted element has to be put into the table n steps from its original hash position.

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

If your hash function is uniform enough, you can calculate the probability of collisions using the birthday problem and from these probabilities calculate the expected probe lengths.