What is the complexity of inserting an element into a hash table?

The average time complexity of inserting an element into a hash table is O(1), meaning the operation runs in constant time.

Why O(1):

1. The hash function quickly computes the index.
2. The element is immediately placed into the right slot (bucket).
3. There is no need to scan other elements.

But in the worst case:

• If there are many collisions,
• or the table is too full, insertion can take O(n), because it will have to search for a free slot or walk through the chain of elements in the bucket.

Summary:

• Average complexity: O(1)
• Worst case: O(n)
• With a good hash function and a sufficiently sized table: insertion is almost always instant.