user1849859 - 3 years ago 142

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?

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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.

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**