Menu
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?
430
Average Case Time Complexity: O(1) for good hash function; O(N) for bad hash function. Space Complexity: O(1) for deletion operation.
In hashing, all the above operations can be performed in O(1) i.e. constant time. It is important to understand that the worst case time complexity for hashing remains O(n) but the average case time complexity is O(1).
The hash key is calculated in O(1) time complexity as always, and the required location is accessed in O(1). Insertion: In the best case, the key indicates a vacant location and the element is directly inserted into the hash table. So, overall complexity is O(1).
Linear probing is a simple collision resolution technique for resolving collisions in hash tables, data structures for maintaining collection of values in a hash table. If there is a collision for the position of the key value then the linear probing technique assigns the next free space to the value.
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
101
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
