Amortized Potential Method

A revision of the Amortized Accounting Method that is stateless and uses a potential function.

Definition

• Given a data structure, let $D$ be size of data structure (size of stack, size of list, etc..)
• Define a potential function $\varphi (D_i)=\text{size of data structure after i operations}$
  • Tracks number of stored elements
  • Tracks distance from threshold
  • Tracks how unbalanced a structure is
• Let $t_i=time(\text{operation i})$
• Let total time $t={\sum }_{i=1}^n{t}_i$
• Let the amortized cost $a_i=t_i+\varphi (D_i)-\varphi (D_{i-1})$
• Then, the total amortized time is: ${\sum }_{i=1}^n{a}_i=t+\varphi (D_n)-\varphi (D_0)$

Proving Process

1. Define $\varphi (D_i)$
2. Show $\varphi (D)\ge 0,\forall D\in \Omega$ (greater than 0 for all states)
3. Prove $\varphi (D_n)\ge \varphi (D_{n_0})$ for all $n>n_0$ sequences of operations
4. Let $t_i=\text{actual time}(\text{operation i})$
5. Then, $a_i=t_i+phi(D_i)-\varphi (D_{i-1})$ (Note that this can be different for diff operations)

Example

• Suppose data structure is Expandable Array
• Define invariant as $\text{capacity}\le 2\ast size$
• Define $\varphi (D)=2\ast size-\text{capacity}$
• Then, $\varphi (D_i)\ge 0,\forall i$
• Prove $\varphi (D_n)-\varphi (D_0)\ge 0,\forall n\ge n_0=0$ operations
• get(), size(), set(i,x) do not change size or capacity, $O(1)$
• add(x):
  • If no copying (no resizing): $a_i=t_i+\varphi (D_i)-\varphi (D_{i-1})=1+(2\ast (s+1)-c)-(2\ast s-c)=3$
  • If copying: $a_i=t_i+\varphi (D_i)-\varphi (D_{i-1})=(c+1)+(2\ast (s+1)-2\ast c)-(2\ast s-c)=3$