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.

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

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

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*^{2})
on the total running time for *n* operations.

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}=iif i - 1 is an exact power of 2

1 Otherwise

As an example, consider the following illustration.

INSERTION

TABLE-SIZE

COST

n

m1

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

^{n}∑_{i=1}c≤^{i}n+^{floor(lgn)}∑_{j=0 }2j

=n+ [2^{floor(lgn)+1}-1]/[2-1] since∑^{n}_{k=0 }x= [^{k}x^{n+1}-1]/[x-1]

=n+ 2^{lgn}. 2-1

=n+ 2n- 1

= 3n- 1

< 3n

Therefore, the amortized cost of a single operation is

=

Total costNumber 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.

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

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

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

size

Φ

Initially, we have num_{0} = size_{0} =0 and Φ_{0 }=
0.

If *i*^{th }insertion does not trigger an expansion, then
size* _{i}*
= size

^{^}c_{i }^{ }= c_{i }+ Φ- Φ_{i}_{i-1}

= 1 + [2 . num- size_{i}] - [2 . num_{i}-1- size_{i}-1]_{i}

= 1 + 2 num- size_{i}- 2(num_{i}- 1) - size_{i}_{i}

= 1 + 2num- size_{i}- 2num_{i}+ 2 - size_{i}_{i}

= 3

If the *i*^{th} insertion does trigger an expansion, then (size of
the table becomes double) then__ ____size__* _{i}* =
size

^{^}c_{i }^{ }= c_{i }+ Φ- Φ_{i}_{i-1 }= num+ [2 . num_{i}- size_{i}] - [2 . num_{i}_{i-1}- size_{i-1}]

= num+ 2num_{i}- size_{i}- 2 . num_{i}_{i-1}+ size_{i-1 }= num+ 2num_{i}-2(num_{i}-1) -2(num_{i }-1) + (num_{i }-1)_{i }

= num+_{i}~~2num~~-_{i}~~2num~~-2 -2num_{i }_{i }+ 2 + num-1_{i }

= 4 -1

= 3

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

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

- Keep the load factor of the dynamic table below by a constant.
- 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.

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.

We start by defining a potential function Φ that is

- 0 immediately after an expansion and builds as the load factor, α(
*T*) =*n/m*, increases to 1. - 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/2size(T) - num[T] if α( T) < 1/2

Note that the potential function is never negative.

When α(*T*) = 1/2

α(*T*) = __ num[ T] __ = 1/2

size[

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[

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[

implies that size[

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.

The subscript is used in the existing notations to denote their values after
the* i ^{th} *operations. That is to say,

Initially

num_{0} = size_{0}
= Φ_{0} = 1 and α_{0}