Performance of Resizing

How long does it take to resize the table? Clearly it is linear with the number of entries. That means that most of the time put takes constant time, but every once in a while ---when we resize---it takes linear time.

At first that sounds bad. Doesn't that undermine my claim that we can perform put in constant time? Well, frankly, yes. But with a little wheedling, I can fix it.

Since some put operations take longer than others, let's figure out the average time for a put operation. The average is going to be c, the constant time for a simple put, plus an additional term of p, the percentage of the time I have to resize, times kn, the cost of resizing.

I don't know what c and k are, but we can figure out what p is. Imagine that we have just resized the hash table by doubling its size. If there are n entries, then we can add an addition n entries before we have to resize again. So the percentage of the time we have to resize is 1/n.

Plugging into the equation, we get

In other words, t(n) is constant time!