Week 02 (38)

Costs for set operations via hash table:

same O(n) behaviour as for single linked list
if sorted: insert/delete = O(n), ∈ = O(n), ∪/∩ = O(n+m)
if unsorted: insert = O(1), delete = O(n), ∈ = O(n), ∪/∩ = O(n.m)
BUT because hash table has H entries ...
- has H lists for n elements (cf. 1 list for n elements)
- each hash table list is, on average, H times shorter than single list
- constants do not appear in O(n) analyses, but can be significant