Hash Collision Linear Probing Running Time

Question

I am trying to do homework with a friend and one question asks the average running time of search, add, and delete for the linear probing method. I think it's O(n) because it has to check at certain number of nodes until it finds an open one to add. And when searching it starts at the original index and moves up until it finds the desired number. But my friends says it's O(1). Which one is right?

Solution

When we talk about Asymptotic complexities we generally take into account very large n. Now for collision handling in a Hash Table some of the methods are chained hashing & linear probing. In both the cases two things may happen (that will help in answering your question): 1. You may require resizing of the hash table due to it getting full 2. Collisions may happen.

In the worst case it will depend on how you have implemented your hash table, say in linear probing you dont find the number,you keep on moving and the number you were looking for was at the end. Here comes the O(n) worst case running time. Coming to chained hashing technique, when a collision happens, to handle them say we have stored the keys in a balanced binary tree so the worst case running time would be O(log n).

Now coming to best case running time, I think there is no confusion, in either case it would be O(1).

O(n) would happen in worst case and not in an average case of a good designed hash table. If that starts happening in average case hash tables wont find a place in Data Structures because then balanced trees on an average would give you O(log n) always and ON TOP OF THAT will preserve the order too.

Sorry to say this but unfortunately your friend is right. Your case would happen in worst case scenarios.

Also look here for more informative stuff i.e. the amortized running time: Time complexity of Hash table