Find the amortized complexity of a Hash function

Question

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.

Answer 1

[edited, my original analysis was for open hashing not open addressing] For 1a) h(x) = x mod N, n < N, so the hash values will be 0, 1, ..., n - 2, 0. All insertions will be collision-free, apart from the last one. The last insertion will use a linear probe. First probe goes to bucket 0, but it is taken and the key is different. The next probe is at slot 1, with same result, until it reaches the first empty bucket at (n - 1). Hence you need (n - 1) extra operations for total of (2n - 1). The amortized cost is (2n - 1)/n per insertion.

For 1b) the hash table degenerates into linked list. Insertion is linear in the size, there are n insertions, hence (n + 1) * n / 2 operations total. That is (n + 1)/2 per insertion.

Answer 2

1a, there will be no collision at all except the last time (N will collide with every value,i.e N will first collide with 0, then you increase the value by one, it will collide with 1, so on and so forth), the total cost would be 1+1+...+1+n = (n-1 times)+n=2n-1, the amortized cost will be (2n-1)/n, it is O(1) with big-O notation.

1b, there will be (i-1) collisions for the i-th insert,plus the insert operation, the cost for the i-th operation would be i. So the total cost will be 1+2+...+n-2+n-1+n=(n+1)*n/2, you have inserted n time, the amortized cost will be (n+1)/2.