What is the average-case time complexity for insert and lookup operations in a well-sized hash table using chaining?

What is the average-case time complexity for insert and lookup operations in a well-sized hash table using chaining?

• A. O(n) average, O(1) worst-case.
• B. O(1) average time for insert and lookups; worst-case O(n) if collisions are heavy.
• C. O(log n) average.
• D. O(n log n) average.

Answer: (B)

Hash tables with chaining spread keys across multiple buckets so that most operations touch a small, separate chain in a bucket. The time to access or insert is dominated by locating the proper bucket (a quick hash computation) and then scanning a short chain there. If the table is well sized, the average number of elements per bucket stays small (the load factor remains a constant), so both insert and lookup run in constant time on average. However, if many keys collide into the same bucket—heavy collisions—the chain in that bucket can become very long, making operations proportional to the chain length, up to n in the worst case. That’s why you see the worst-case O(n). The alternative options reflect other data structures or scenarios, not the typical behavior of a well-sized hash table with chaining.

Hash tables with chaining spread keys across multiple buckets so that most operations touch a small, separate chain in a bucket. The time to access or insert is dominated by locating the proper bucket (a quick hash computation) and then scanning a short chain there. If the table is well sized, the average number of elements per bucket stays small (the load factor remains a constant), so both insert and lookup run in constant time on average.

However, if many keys collide into the same bucket—heavy collisions—the chain in that bucket can become very long, making operations proportional to the chain length, up to n in the worst case. That’s why you see the worst-case O(n). The alternative options reflect other data structures or scenarios, not the typical behavior of a well-sized hash table with chaining.