Re:Finding unique items: hash vs. sort
by aidenn0 on Wednesday January 08, 2020 @12:32AM
(#21988636)
If you do O(N) work every time the hashmap is "full" and double the size of the hashmap, it's still O(N).
Hand-wavy proof:
If your last insert caused a rehash, then you have done O(N) work plus O(N/2) plus O(N/4)... the limit of which is equal to O(2N), and thus only a constant factor more.
Hand-wavy proof:
If your last insert caused a rehash, then you have done O(N) work plus O(N/2) plus O(N/4)... the limit of which is equal to O(2N), and thus only a constant factor more.