Table expansion

It is often necessary to create a table before it is known how much space is needed. One possible strategy is to double the size of the table when it is full. Here we will use the accounting method to show that the amortized cost of an insertion operation in such a table is O(1).

Before looking at the procedure in detail, we need some definitions. Let T be a table, E an element to insert, num(T) the number of elements in T, and size(T) the allocated size of T. We assume the existence of operations create_table(n), which creates an empty table of size n, for now assumed to be free, and elementary_insert(T,E), which inserts element E into a table T that already has space allocated, with a cost of 1.

The following pseudocode illustrates the table insertion procedure:

function table_insert(T, E)
    if num(T) = size(T)
        U := create_table(2 × size(T))
        for each F in T
            elementary_insert(U, F)
        T := U
    elementary_insert(T, E)

Without amortized analysis, the best bound we can show for n insert operations is O(n) — this is due to the loop at line 4 that performs num(T) elementary insertions.

For analysis using the accounting method, we assign a payment of 3 to each table insertion. Although the reason for this is not clear now, it will become clear during the course of the analysis.

Assume that initially the table is empty with size(T) = m. The first m insertions therefore do not require reallocation and only have cost 1 (for the elementary insert). Therefore, when num(T) = m, the pool has (3 - 1)×m = 2m.

Inserting element m + 1 requires reallocation of the table. Creating the new table on line 3 is free (for now). The loop on line 4 requires m elementary insertions, for a cost of m. Including the insertion on the last line, the total cost for this operation is m + 1. After this operation, the pool therefore has 2m + 3 - (m + 1) = m + 2.

Next, we add another m - 1 elements to the table. At this point the pool has m + 2 + 2×(m - 1) = 3m. Inserting an additional element (that is, element 2m + 1) can be seen to have cost 2m + 1 and a payment of 3. After this operation, the pool has 3m + 3 - (2m + 1) = m + 2. Note that this is the same amount as after inserting element m + 1. In fact, we can show that this will be the case for any number of reallocations.

It can now be made clear why the payment for an insertion is 3. 1 pays for the first insertion of the element, 1 pays for moving the element the next time the table is expanded, and 1 pays for moving an older element the next time the table is expanded. Intuitively, this explains why an element's contribution never "runs out" regardless of how many times the table is expanded: since 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 ${\displaystyle {\frac {m}{2}}}$ entries to help pay for the new table. Those entries already paid for the current table. We must then rely on the last ${\displaystyle {\frac {m}{2}}}$ entries to pay the cost ${\displaystyle 2m}$. This means we must add ${\displaystyle {\frac {2m}{m/2}}=4}$ to the payment for each entry, for a total payment of 3 + 4 = 7.