If the allocated space for the table is not enough, we must copy the table into larger size table. Similarly, if large number of members erased from the table, it is good idea to reallocate the table with a smaller size. Using amortized analysis we shall show that the amortized cost of insertion and deletion is constant and unused space in a dynamic table never exceeds a constant fraction of the total space.

Assume that the dynamic table supports following two operations:

TABLE-INSERT

This operation add an item in the table by copying into the unused single slot. The cost of insertion is 1.

 

TABLE-DELETE

This operation removes an item from the table by freeing a slot. The cost of deletion is 1.

Load Factor

The number of items stored in the table, n, divided by the size of the table, m, is defined as the load factor and denoted as T(α) = m/n
The load factor of the empty table (size m=0) is 1.
A table is full when there exists no used slots. That is, the number of items stored in the table equals the number of available slots (m=n). In this case

Load factor     T(α) = n/m = 1

Proposed Algorithm

1. Initialize table size to m=1.
2. Keep inserting elements as long as size of the table less than number of items i.e., n<m.
3. Generate a new table of size 2m and set m <-- 2m.
4. Copy items (by using elementary insertion) from the old table into the new one.
5. GOTO step 2.

Analysis

If n elementary insert operations are performed in line 4, the worst-case cost of an operation is O(n), which leads to an upper bound of O(n²) on the total running time for n operations.

Aggregate Analysis

The i^th insert operation causes an expansion only when i - 1 an exact power of 2. Let c_i be the cost of the i^th insert operation. Then

c_i = i         if i - 1 is an exact power of 2
      1         Otherwise

As an example, consider the following illustration.

INSERTION	TABLE-SIZE	COST
n	m	1
1	1	1+1
2	2	1+2
3	4	1
4	4	1+4
5	8	1
6	8	1
7	8	1
8	8	1
9	16	1+8
10	16	1

The total cost of n insert operations is therefore

ⁿ∑_i=1 cⁱ ≤ n + ^floor(lgn)∑_j=0 2j
              = n + [2^floor(lgn)+1 -1]/[2-1]       since ⁿ∑_k=0 x^k = [xⁿ⁺¹ -1]/[x-1]
              = n + 2^lgn . 2-1
              = n + 2n - 1
              = 3n - 1
              < 3n

Therefore, the amortized cost of a single operation is

=              Total cost               
       Number of operations
=   3n/n
=   3

Asymptotically, the cost of dynamic table is O(1) which is the same as that of table of fixed size.

Accounting Method

Here we guess charges to 3$. Intuitively, each item pays for 3 elementary operations.

1. 1$ for inserting immediate item.
2. 1$ for moving item (re-insert) when the table is expanded.
3. 1$ for moving another item (re-insert) has already been moved once when that table is expanded.

Potential Method

Define a potential function Φ that is 0 immediately after an expansion but potential builds to the table size by the time the table is full.

Φ(T) = 2 . num[T] - size[T]

Immediately after an expansion (but before any insertion) we have, num[T] = size[T]/2

which implies

Φ(T) = 2 . num[T] - 2 num[T]
        = 0

Immediately before an expansion, we have num[T] = size[T],

which implies

Φ(T) = 2 . num[T] - num[T]
        = num[T]

The initial value of the potential function is zero i.e., Φ(T) = 0, and half-full i.e., num[T] ≥ size[T]/2. or 2 num[T] ≥ size[T]

which implies

           Φ(T) = 2 num[T] - size[T] ≥ 0

That is, Φ(T) is always nonnegative.

Before, analyze the amortized cost of the i^th TABLE-INSERT operation define following.

Let
           num_i = number of elements in the table after i^th operation
           size_i  = table after i^th operation.
              Φ_i = Potential function after i^th operation.

Initially, we have num₀ = size₀ =0 and Φ₀ = 0.

If i^th insertion does not trigger an expansion, then size_i = size_i-1 and the amortized cost of the operation is

^{^}c_i   =  c_i + Φ_i - Φ_i-1
      = 1 + [2 . num_i - size_i] - [2 . num_i-1- size_i-1]
      = 1 + 2 num_i - size_i - 2(num_i- 1) - size_i
      = 1 + 2num_i - size_i - 2num_i + 2 - size_i
      = 3

If the i^th insertion does trigger an expansion, then (size of the table becomes double) then size_i = size_i-1 = num_i and the amortized cost of the operation is 2

^{^}c_i   =  c_i + Φ_i - Φ_i-1
        =  num_i + [2 . num_i - size_i] - [2 . num_i-1 - size_i-1]
      =  num_i + 2num_i - size_i - 2 . num_i-1 + size_i-1
        =  num_i + 2num_i -2(num_i -1) -2(num_i -1) + (num_i -1)
      =  num_i + 2num_i - 2num_i -2 -2num_i +  2 + num_i -1
      =  4 -1
      =  3

What is the catch?    It show how potential builds (from zero) to pay the table expansion.

Dynamic Table Expansion and Contraction

When the load factor of the table, α(T) = n/m, becomes too  small, we want to preserve following two properties:

1. Keep the load factor of the dynamic table below by a constant.
2. Keep the amortized cost of the dynamic table bounded above by a constant.

Proposed Strategy

Even:   When an item is inserted into full table.
Action: Double the size of the table i.e., m ← 2m.
Even:    When removing of an item makes table less the half table.
Action:  Halve the size of the table i.e., m ← m/2.

The problem with this strategy is trashing. We can avoid this problem by allowing the load factor of the table, α(T) = n/m, to drop below 1/2 before contradicting it. By contradicting the table when load factor falls below 1/4, we maintain the lower bound α(T) ≥ 1/4 i.e., load factor is bounded by the constant 1/4.

Load Factor

The load factor α(T), of non-empty table T is defined as the number of items stored in the T divided by the size of T, which is number slots in T, i.e.,

         α(T) =   num[T] / size[T] 

Since for an empty table, we have

num[T] = size[T] = 0 and  α(T) = 1

which implies that we always have

          num[T] = α(T) . size[T]

whether table is empty or not.

Analysis by Potential Method

We start by defining a potential function Φ that is

1. 0 immediately after an expansion and builds as the load factor, α(T) = n/m,  increases to 1.
2. 0 immediately after a contraction and builds as the load factor, α(T) = n/m, decreases to 1/4.

Φ(T)	2 . num[T] - size(T)       if α(T) ≥ 1/2
	size(T) - num[T]            if α(T) < 1/2

Note that the potential function is never negative.

Properties of Potential Function

When α(T) = 1/2

α(T) =   num[T]   = 1/2
              size[T] 

implies that size[T] = 2 num[T]

And the potential function is

since Φ(T) = 2 num[T] - size[T]
                 = 2 num[T] - 2 num[T]
                 = 0

When α(T) = 1
since   α(T) =     num[T]   = 1
                          size[T] 

implies that size[T] = num[T]

And the potential function is

since Φ(T) = 2 num[T] - size[T]
                 = 2 num[T] - num[T]
                 = num[T]

which indicates that the potential can pay for an expansion if an item is inserted.

When α(T) = 1/4, then
since  α(T) =    num[T]   = 1/4
                        size[T] 
implies that  size[T] = 4 num[T]

And the potential function is

Φ(T)  = size[T]/2 - num[T]
         = 4 num[T]/2 - num[T]
         = num[T]

which indicates that the potential can pay for a contradiction if an item is deleted.

Notation

The subscript is used in the existing notations to denote their values after the i^th operations. That is to say, ^{^}c_i, c_i, num_i, size_i, α_i and Φ_i indicate values after the  i^th  operation.

Initially
          num₀ = size₀ = Φ₀ = 1 and α₀