Dynamic Table

 

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(n2) on the total running time for n operations.

 

Aggregate Analysis

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


ci = 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

ni=1 cin + floor(lgn)j=0 2j
              = n + [2floor(lgn)+1 -1]/[2-1]       since
nk=0
xk = [xn+1 -1]/[x-1]
              = n + 2lgn . 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 ith TABLE-INSERT operation define following.

Let
           numi = number of elements in the table after ith operation
           sizei  = table after ith operation.
              Φi = Potential function after ith operation.

Initially, we have num0 = size0 =0 and Φ0 = 0.

 

If ith insertion does not trigger an expansion, then sizei = sizei-1 and the amortized cost of the operation is

^ci   =  ci + Φi - Φi-1
      = 1 + [2 . numi - sizei] - [2 . numi-1- sizei-1]
      = 1 + 2 numi - sizei - 2(numi- 1) - sizei
      = 1 + 2numi - sizei - 2numi + 2 - sizei
      = 3

 

If the ith insertion does trigger an expansion, then (size of the table becomes double) then sizei = sizei-1 = numi and the amortized cost of the operation is 2

^ci   =  ci + Φi - Φi-1
       
=  numi + [2 . numi - sizei] - [2 . numi-1 - sizei-1]
      =  numi + 2numi - sizei - 2 . numi-1 + sizei-1
       
=  numi + 2numi -2(numi -1) -2(numi -1) + (numi -1)
      =  numi + 2numi - 2numi -2 -2numi +  2 + numi -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 ith operations. That is to say, ^ci, ci, numi, sizei, αi and Φi indicate values after the  ith  operation.

Initially
          num0 = size0 = Φ0 = 1 and α
0