0

hello,
I have a question about hashtable.
what is the complexity of searching an item in hashtable in average case performance (when using a rehash function)?

thank you!

4
Contributors
3
Replies
4
Views
7 Years
Discussion Span
Last Post by jk451
0

>what is the complexity of searching an item in hashtable in average case performance
Amortized O(1). While an individual search might be more expensive, in toto the performance is constant. This is all assuming the hash table is properly implemented, of course.

0

>what is the complexity of searching an item in hashtable in average case performance
Amortized O(1). While an individual search might be more expensive, in toto the performance is constant. This is all assuming the hash table is properly implemented, of course.

I would say that the last 2 sentences were the answer to "what is the complexity in the average case...".

Note, though, that it is not amortized O(1). That would mean that any sequence of n legal operations during the lifetime of the hash table takes O(n), i.e. amortized complexity is like the normal complexity, except it gives you solid upper bound on a sequence of operations and it is a kind of misleading convention that when saying "amortized O" you give as the argument (upper bound on sequence/# of ops. in sequence).

So, assuming you can create a pathological input sequence for any arbitrary hashtable, even amortized complexity is O(n).

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.