Find the amortized complexity of a Hash function

Viewed 544

enter image description here

I was studying for my final when I ran into this problem.
For 1a, I think its O(1) for amortized complexity, because it does x mod N which is sparse enough and linear probing incase it fails However I'm not sure how to state or prove that exactly.

For 1b, it would hash into the same place, so it would linearly probe more each time it inserts, but I'm not sure how to derive a runtime from that either.

2 Answers
Related