user1849859 - 6 months ago 57

C++ Question

What's the average case for the search function in a hash table with collisions resolved through separate chaining? In the best case is Θ(1), in the worst case is Θ(n) but what about the average case? And how do I demonstrate the complexity for the average case?

Answer

It's still O(1), assuming the hash table implementation provides some threshold for size() / buckets, beyond which it resizes (as per std::unordered map). You can easily see this - if you searched for every element in the hash table then the average is going to be a linear multiple of O(1) where that linear factor is the loading factor above.... Linear factors are removed during big-O analysis.