Hash Collision Linear Probing Running Time

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?

Answers


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


Need Your Help

Unable to start activity - ComponentInfo error

java android runtimeexception

This are the errors I get when I try to start my app.

Webapi - .Net restful put/update parameter convention on service/repo layers

c# .net rest service asp.net-web-api

I have a question about the standard way to perform a restful update.

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.