the table is always doubled, the newest half always covers the cost of moving the oldest half. We initially assumed that creating a table was free. In reality, creating a table of size n may be as expensive as O(n). Let us say that the cost of creating a table of size n is n. Does this new cost present a difficulty? Not really; it turns out we use the same method to show the amortized O(1) bounds. All we have to do is change the payment. When a new table is created, there is an old table with m entries. The new table will be of size 2m. As long as the entries currently in the table have added enough to the pool to pay for creating the new table, we will be all right. We cannot expect the first entries to help pay for the new table. Those entries already paid for the current table. We must then rely on the last entries to pay the cost . This means we must add to the payment for each entry, for a total payment of 3 + 4 = 7. References Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Section 17.2: The accounting method, pp. 410–412. Analysis of algorithms