The Java Course provides a general introduction to programming in Java. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details. 
Home Table Performance of Resizing  
See also: Performance Analysis  
Search the VIAS Library  Index  
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 resizeit 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!


Home Table Performance of Resizing 