Hash Table creation runtime complexity

Question

An insert into a hash table has a worst case complexity of O(n).

But when creating a new hash table and inserting n elements, as far as I understand this would result in n insertions into a growing hash table. Therefore, O(1) + O(2) + O(3) + ... + O(n) = O((n^2+n)/2). So worst runtime complexity of creating a hash table with n elements would be quadratic. Is this correct?

However, average and amortized runtime complexity of inserts are O(1), therefore average and amortized runtime complexity of creating a hashmap with n elements would also be O(1)?

Tomer Arazy · Accepted Answer · 2024-03-13 13:11:46Z

0

If you resize by 1 (or any other constant) on each insertion then you don't get O(1) but rather O(n) like your analysis showed.

Instead we resize by rather by some factor of the current number of elements in the hash table, the for example you double the size of the hash table whenever it gets filled (in reality we'll some load factor and don't wait until it's filled).

So for example if the number of items in your hash table is n and it was just resized then the maximum possible number of items is 2n. So now for the next resize to happen your need to perform at least n insertions and then resize is also O(n) so amortized is O(1).

answered Mar 13, 2024 at 13:11

Tomer Arazy

1,82311 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Hash Table creation runtime complexity

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related