Amortized Analysis in DAA

Amortized Analysis

• Aggregate Method
• Accounting Method
• Potential Method
• Dynamic Table

Amortized Analysis

In an amortized analysis, the time required to perform a sequence of data structure operations is average over all operation performed. Amortized analysis can be used to show that average cost of an operation is small, if one average over a sequence of operations, even though a single operation might be expensive. Unlike the average probability distribution function, the amortized analysis guarantees the 'average' performance of each operation in the worst case.
CLR covers the three most common techniques used in amortized analysis. The main difference is the way the cost is assign.

1. Aggregate Method
   • Computes an upper bound T(n) on the total cost of a sequence of n operations.
2. Accounting Method
   • Overcharge some operations early in the sequence. This 'overcharge' is used later in the sequence for pay operation that charges less than they actually cost.
3. Potential Method
   • Maintain the credit as the potential energy to pay for future operations.

 

Aggregate Method

Aggregate Method Characteristics

• It computes the worst case time T(n) for a sequence of n operations.
• The amortized cost is T(n)/n per operation.
• It gives the average performance of each operation in the worst case.
• This method is less precise than other methods, as all operations are assigned the same cost.

Application 1: Stack operations
In the following pseudocode, the operation STACK-EMPTY returns TRUE if there are no object currently on the stack, and FALSE otherwise.

1. Worst-case cost for MULTIPOP is O(n). There are n successive calls to MULTIPOP would cost O(n²). We get unfair cost O(n²) because each item can be poped only once for each time it is pushed.
    
2. In a sequence of n mixed operations the most times multipop can be called n/2.Since the cost of push and pop is O(1), the cost of n stack operations is O(n). Therefore, amortized cost of an operation is the average: O(n)/n = O(1).

Application 2: Binary Counter

We use an array A[0 . . k-1] of bits, where length [A] = k, as the counter. A binary number x that is stored in the counter has its lowest-order bit in A[0] and its highest-order bit is A[k-1], so that   ^k-1S_i=0 2ⁱA[i]. Initially, x = 0, and thus A[i] = 0 for i=0, 1, . . . , k-1.
To add 1 (modulus 2^k ) to the value in the counter, use the following pseudocode.

A single execution of  INCREMENT takes O(k) in worst case when Array A contains all 1's. Thus, a sequence of n INCREMENT operation on an initially zero counter takes O(nk) in the worst case. This bound is correct but not tight.

We can tighten the analysis to get a worst-case cost for a sequence of an INCREMENT's by observing that not all bits flip each time INCREMENT is called.

Bit A[0] is changed ceiling n times (every time)
Bit A[0] is changed ceiling [n/2¹] times (every other time)
Bit A[0] is changed ceiling [n/2²] times (every other time)
        .
        .
        .
Bit A[0] is changed ceiling [n/2ⁱ] times.

In general, for i = 0, 1, . . ., lg n, bit A[i] flips n/2ⁱ times in a sequence of n INCREMENT operations on an initially zero counter.
For i > lg(n), bit A i never flips at all. The total number of flips in a sequence is thus
        ^floor(log)S_i=0  n/2ⁱ < n ^∞S_i=0  1/2ⁱ  = 2n
Therefore, the worst-case time for a sequence of n INCREMENT operation on an initially zero counter is therefore O(n), so the amortized cost of each operation is O(n)/n =O(1).

 

Accounting Method

 

In this method, we assign changes to different operations, with some operations charged more or less than they actually cost. In other words, we assign artificial charges to different operations.

• Any overcharge for an operation on an item is stored (in an bank account) reserved for that item.
• Later, a different operation on that item can pay for its cost with the credit for that item.
• The balanced in the (bank) account  is not allowed to become negative.
• The sum of the amortized cost for any sequence of operations is an upper bound for the actual total cost of these operations.
• The amortized cost of each operation must be chosen wisely in order to pay for each operation at or before the cost is incurred.

Application 1: Stack Operation
Recall the actual costs of stack operations were:

The amortized cost assignments are

PUSH                     2
POP                        0
MULTIPOP            0

Observe that the amortized cost of each operation is O(1). We must show that one can pay for any sequence of stack operations by charging the amortized costs.

The two units costs collected for each PUSH is used as follows:

• 1 unit is used to pay the cost of the PUSH.
• 1 unit is collected in advanced to pay for a potential future POP.

Therefore, for any sequence for n PUSH, POP, and MULTIPOP operations, the amortized cost is an

C_i   =  ^j=1S_i  3 - C_iactual      = 3i - (2^{floor(lg1) + 1} + i -floor(lgi) - 2)
If i  = 2^k, where k ≥ 0, then
C_i   = 3i - (2^k+1 + i - k -2)
      = k + 2
If i  = 2^k + j, where k ≥ 0 and 1 ≤  j ≤  2^k, then
C_i  = 3i - (2^k+1 + i - k - 2)
     = 2j + k + 2

This is an upperbound on the total actual cost. Since the total amortized cost is O(n) so is the total cost.

As an example, consider a sequence of n operations is performed on a data structure. The i^th operation costs i if i is an exact power of 2, and 1 otherwise. The accounting method of amortized analysis determine the amortized cost per operation as follows:
Let amortized cost per operation be 3, then the credit C_i after the i^th operation is: Since k ≥ 1 and j ≥ 1, so credit C_i always greater than zero. Hence, the total amortized cost 3n, that is O(n) is an upper bound on the total actual cost. Therefore, the amortized cost of each operation is O(n)/n = O(1).
Another example, consider a sequence of stack operations on a stack whose size never exceeds k. After every k operations, a copy of the entire stack is made. We must show that the cost of n stack operations, including copying the stack, is O(n) by assigning suitable amortized costs to the various stack operations.
There are, ofcourse, many ways to assign amortized cost to stack operations. One way is:

PUSH                        4,
POP                           0,
MULTIPOP               0,
STACK-COPY         0.

Every time we PUSH, we pay a dollar (unit) to perform the actual operation and store 1 dollar (put in the bank). That leaves us with 2 dollars, which is placed on x (say) element. When we POP x element off the stack, one of two dollar is used to pay POP operation and the other one (dollar) is again put into a bank account. The money in the bank is used to pay for the STACK-COPY operation. Since after kk dollars in the bank and the stack size is never exceeds k, there is enough dollars (units) in the bank (storage) to pay for the STACK-COPY operations. The cost of n stack operations, including copy the stack is therefore O(n). operations, there are atleast


Application 2: Binary Counter
We observed in the method, the running time of INCREMENT operation on binary counter is proportion to the number of bits flipped. We shall use this running time as our cost here.
For amortized analysis, charge an amortized cost of 2 dollars to set a bit to 1.
When a bit is set, use 1 dollar out of 2 dollars already charged to pay the actual setting of the bit, and place the other dollar on the bit as credit so that when we reset a bit to zero, we need not charge anything.
The amortized cost of psuedocode  INCREMENT can now be evaluated:

1. i = 0
2. while i < length[A] and A[i] = 1
3.         do A[i] = 0
4.             i = i +1
5. if i < length [A]
6.             then A[i] = 1

Within the while loop, the cost of resetting the bits is paid for by the dollars on the bits that are reset.At most one bit is set, in line 6 above, and therefore the amortized cost of an INCREMENT operation is at most 2 dollars (units). Thus, for n INCREMENT operation, the total amortized cost is O(n), which bounds the total actual cost.


Consider a Variant
Let us implement a binary counter as a bit vector so that any sequence of n INCREMENT and RESET operations takes O(n) time on an initially zero counter,. The goal here is not only to increment a counter but also to read it to zero, that is, make all bits in the binary counter to zero. The new field , max[A], holds the index of the high-order1 in A. Initially, set max[A] to -1. Now, update max[A] appropriately when the counter is incremented (or reset). By contrast the cost of RESET, we can limit it to an amount that can be covered from earlier INCREMENT'S.

1. i = 1
2. while i < length [A] and A[i] = 1
3.     do A[i] = 0
4.         i = i +1
5. if i < length [A]
6.     then A[i] = 1
7.     if i > max[A]
8.         then max[A] = i
9.         else max[A] = -1

Note that lines 7, 8 and 9 are added in the CLR algorithm of binary counter.

For i = 0 to max[A]
        do A[i] = 0
max[A] = -1

For the counter in the CLR we assume that it cost 1 dollar to flip a bit. In addition to that we assume that we need 1 dollar to update max[A]. Setting and Resetting of bits work exactly as the binary counter in CLR: Pay 1 dollar to set bit to 1 and placed another 1 dollar on the same bit as credit. So, that the credit on each bit will pay to reset the bit during incrementing.
In addition, use 1 dollar to update max[A] and if max[A] increases place 1 dollar as a credit on a new high-order 1. (If max[A] does not increase we just waste that one dollar). Since RESET manipulates bits at some time before the high-order 1 got up to max[A], every bit seen by RESET has one dollar credit on it. So, the zeroing of bits by RESET can be completely paid for by the credit stored on the bits. We just need one dollar to pay for resetting max[A].
Thus, charging 4 dollars for each INCREMENT and 1 dollar for each RESET is sufficient, so the sequence of n INCREMENT and RESET operations take O(n) amortized time.

 

Potential Method

This method stores pre-payments as potential or potential energy that can be released to pay for future operations. The stored potential is associated with the entire data structure rather than specific objects within the data structure.
Notation:

• D₀ is the initial data structure (e.g., stack)
• D_i is the data structure after the i^th operation.
• c_i is the actual cost of the i^th operation.
• The potential function Ψ maps each D_i to its potential value Ψ(D_i)

The amortized cost  ^{^}c_i  of the ith operation w.r.t potential function Ψ is defined by

^{^}c_i   =  c_i + Ψ(D_i) - Ψ (D_i-1)  --------- (1)

The amortized cost of each operation is therefore

^{^}c_i   =  [Actual operation cost] + [change in potential].

By the eq.I, the total amortized cost of the n operation is

ⁿ_i=1 ^{^}c_i   =  ⁿ_i=1(c_i   + Ψ(D_i) - Ψ (D_i-1) )
                =  ⁿ_i=1 c_i   +  ⁿ_i=1 Ψ(D_i) - ⁿ_i=1Ψ (D_i-1)
                =  ⁿ_i=1 c_i   + Ψ(D₁) + Ψ(D₂) +  . . . + Ψ (D_n-1) + Ψ(D_n) - {Ψ(D₀) + Ψ(D₁) + . . . + Ψ (D_n-1)
                =  ⁿ_i=1 c_i   + Ψ(D_n) - Ψ(D₀)   ----------- (2)

If  we define a potential function Ψ so that Ψ(D_n)   ≥ Ψ(D₀), then the total amortized cost  ⁿ_i=1 ^{^}c_i  is an upper bound on the total actual cost.
As an example consider a sequence of n operations performed on a data structure. The i^th operation costs i if i is an exact power of 2 and 1 otherwise. The potential method of amortized determines the amortized cost per operation as follows:

         Let  Ψ(D_i) = 2i - 2^ëlgi+1û + 1, then
                Ψ(D₀) = 0. Since 2^ëlgi+1û  ≤  2i where i >0 ,
Therefore,  Ψ(D_i)  ≥ 0 = Ψ(D₀)

If i = 2k where k ≥ 0 then

2^ëlgi+1û  = 2^k+1  = 2i
   2^ëlgiû  = 2^k  = i

 ^{^}c_i   =  c_i  + Ψ(D_i) - Ψ(D_i-1)
            = i + (2i -2i+1) -{2(i-1)-i+1}
            = 2

If i = 2^k  + j where k  ≥ 0 and 1 ≤  j  ≤  2^kthen 2^ëlgi+1û = 2^[lgi]

   ^{^}c_i   =  c_i  + Ψ(D_i) - Ψ(D_i-1) = 3
 

Because  ⁿ_i=1^{^}c_i    =  ⁿ_i=1 c_i   + Ψ(D_n) - Ψ(D₀)

and Ψ(D_i)  ≥ Ψ(D₀), so, the total amortized cost of n operation is an upper bound on the total actual cost. Therefore, the total amortized cost of a sequence of noperation is O(n) and the amortized cost per operation is O(n) / n = O(1).


Application 1- Stack Operations
Define the potential function Ψ on a stack to be the number of objects in the stack. For empty stack D₀ , we have Ψ(D₀) = 0. Since the number of objects in the stack can not be negative, the stack D_i after the i^th operation has nonnegative potential, and thus

Therefore, the total amortized cost of n operations w.r.t. function Ψ represents an upper bound on the actual cost.
Amortized costs of stack operations are:
 

PUSH
 

If the i^th operation on a stack containing s object is a PUSH operation, then the potential difference is

Ψ(D_i) - Ψ(D_i-1) = (s + 1) - s = 1

In simple words, if  i^th is PUSH then (i-1)^th must be one less. By equation I, the amortized cost of this PUSH operation is

     ^{^}c_i   =  c_i  + Ψ(D_i) - Ψ(D_i-1) = 1 + 1 = 2

MULTIPOP
 

If the i^th operation on the stack is MULTIPOP(S, k) and k` = min(k,s) objects are popped off the stack.
The actual cost of the operation is k`, and the potential difference is

Ψ(D_i) - Ψ(D_i-1) =  -k`

why this is negative? Because we are taking off item from the stack. Thus, the amortized cost of the MULTIPOP operation is

    ^{^}c_i   =  c_i  + Ψ(D_i) - Ψ(D_i-1) = k`-k` = 0

POP

Similarly, the amortized cost of a POP operation is 0.

Analysis
Since amortized cost of each of the three operations is O(1), therefore, the total amortized cost of n operations is O(n). The total amortized cost of n operations is an upper bound on the total actual cost.


Lemma     If data structure is Binary heap: Show that a potential function is O(nlgn) such that the amortized cost of EXTRACT-MIN is constant.

Proof
We know that the amortized cost ^{^}c_i of operation i is defined as

^{^}c_i   =  c_i  + Ψ(D_i) - Ψ(D_i-1)

For the heap operations, this gives us

c₁lgn = c₂lg(n+c₃) + Ψ(D_i) - Ψ(D_i-1)        (Insert) ------------(1)

c₄ = c₅lg(n + c₆) + Ψ(D_i) - Ψ(D_i-1)          (EXTRACT-MIN) -----(2)

Consider the potential function Ψ(D) = lg(n!), where n is the number of items in D.

From equation (1), we have

    (c₁ - c₂)lg(n + c₃) = lg(n!) - lg ((n-1)!) = lgn.
This clearly holds if c₁ = c₂ and c₃ = 0.

From equation (2), we have

    c₄ - c₅ lg(n + c₆) = lg(n!) - lg ((n+1)!) =  - lg(n+1).
This clearly holds if c₄ = 0 and c₄ = c₆ = 1.

Remember that stirlings function tells that lg(n!) = θ(nlgn), so

    Ψ(D) = θ(n lg n)

And this completes the proof.


Application 2: Binary Counter
Define the potential of the counter after i^th INCREMENT operation to be b_i, the number of 1's in the counter after i^th operation.
Let i^th INCREMENT operation resets t_i bits. This implies that actual cost = atmost (t_i + 1).
Why? Because in addition to resetting t_i it also sets at most one bit to 1.
Therefore, the number of 1's in the counter after the i^th operation is therefore b_i ≤  b_i-1 - t_i + 1, and the potential difference is

Ψ(D_i) - Ψ(D_i-1)  ≤  (b_i-1 - t_i + 1) - b_i-1 = 1- t_i

Putting this value in equation (1), we get

    ^{^}c_i    =     c_i + Ψ(D_i) - Ψ (D_i-1)           =     (t_i + 1) + (1- t_i)           =     2

If counter starts at zero, then Ψ(D₀) = 0. Since Ψ(D_i) ≥ 0 for all i, the total amortized cost of a sequence of n INCREMENT operation is an upper bound on the total actual cost, and so the worst-case cost of n INCREMENT operations is O(n).
If counter does not start at zero, then the initial number are 1's (= b₀).
After 'n' INCREMENT operations the number of 1's = b_n, where 0 ≤  b₀, b_n ≤  k.

Since   ⁿ_i=1^{^}c_i  = (c_i  + Ψ(D_i) + Ψ(D_i-1))
=>        ⁿ_i=1^{^}c_i  =  ⁿ_i=1 c_i  +  ⁿ_i=1 Ψ(D_i) +  ⁿ_i=1 Ψ(D_i-1)
=>        ⁿ_i=1^{^}c_i  =  ⁿS_i=1 c_i  +   Ψ(D_n) -  Ψ(D₀)
=>         ⁿ_i=1c_i  =  ⁿ_i=1 ^{^}c_i  +  Ψ(D₀) -  Ψ(D_n)

We have ^{^}c_i  ≤ 2 for all 1≤ i ≤ n. Since Ψ(D_i) = b₀ and Ψ(D_n) = b, the total cost of n INCREMENT operation is

Since ⁿ_i=1c_i  =  ⁿ_i=1 ^{^}c_i  +  Ψ(D_n) +  Ψ(D₀)                  ≤ ⁿ_i=1 2  - b_n +  b₀  why because c_i  ≤ 2                  = 2 ⁿ_i=1   - b_n +  b₀                   = 2n - bn + b

Note that since b₀ ≤ k, if we execute at least n = Ω(k) INCREMENT Operations, the total actual cost is O(n), no matter what initial value of counter is.

Implementation of a queue with two stacks, such that the amortized cost of each ENQUEUE and each DEQUEUE Operation is O(1). ENQUEUE pushes an object onto the first stack. DEQUEUE pops off an object from second stack if it is not empty. If second stack is empty, DEQUEUE transfers all objects from the first stack to the second stack to the second stack and then pops off the first object. The goal is to show that this implementation has an O(1) amortized cost for each ENQUEUE and DEQUEUE operation. Suppose D_i denotes the state of the stacks after i^th operation. Define Ψ(D_i) to be the number of elements in the first stack. Clearly, Ψ(D₀) = 0 and Ψ(D_i)  ≥ Ψ(D₀) for all i. If the i^th operation is an ENQUEUE operation, then Ψ(D_i) - Ψ(D_i-1) = 1
Since the actual cost of an ENQUEUE operation is 1, the amortized cost of an ENQUEUE operation is 2. If the i^th operation is a DEQUEUE, then there are two case to consider.

Case i: When the second stack is not empty.

 

In this case we have Ψ(D_i) - Ψ(D_i-1) = 0 and the actual cost of the DEQUEUE operation is 1.

 

 

Case ii: When the second stack is empty.

 

In this case, we have Ψ(D_i) - Ψ(D_i-1) =   - Ψ(D_i-1) and the actual cost of the DEQUEUE operation is Ψ(D_i-1) + 1

.

In either case, the amortize cost of the DEQUEUE operation is 1. It follows that each operation has O(1) amortized cost
 

 

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

 

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 noperations.

 

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

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
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.,

Since for an empty table, we have

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

which implies that we always have
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 α₀