CODEWITHSUNDEEP
data-structurestime-complexitybig-ohashtable
frieren
frieren

Reputation: 3

Big O - Creating Hashtable with values - Timecomplexity

Me and my fellow students have been debating for a good time what the big o notation for this is: Creating a hashtable with values by iterative insertion (the number of elements is known at the beginning) in the average and worst case.

Average complexity of inserting 1 element is O(1) so inserting n elements in an empty hashtable should be O(n).

Worst case insertion of 1 element is O(n). So is inserting n elements in an empty hashtable O(n^2) or O(n) and why?

Upvotes: 0

Views: 80

Answers (1)

SomeWittyUsername
SomeWittyUsername

Reputation: 18338

Worst case happens when every insertion results in collision. The cost of collision depends on the hash table implementation. The simplest implementation is usually a linked list of all elements that belong to the same hash cell. So insertion of n elements will cost 1+2+3+..+n time units. This is a sum of arithmetic series and it equals n(n+1)/2=O(n2). This result can be improved by using more advanced data structures to handle collisions. For example, for AVL tree the cost of insertion is O(logn), i.e., for n elements it will be O(log1+log2+...+logn)=O(log(n!)) which is significantly better than O(n2).

Upvotes: 1

Related Questions