Amortized Accounting Method

A method for counting Amortized Time.

Method

• Assign each operation to receive fixed credit amount $x$.
• Assign each operation an artificial cost to each operation (no need to be actual cost)
• Some operations keep extra and that amount is stored as credit to pay more expensive operations later.
• Prove invariant ($amount\ge 0$) $⟹$ Each operation takes $O(x)$ amortized time

Example

Suppose a multi-pop Stack with:

• Push: push a element to top of stack $O(1)$
• Pop: pop top element off stack $O(1)$
• Multi-Pop: pop top $n$ element off stack $O(n)$ Then, we assign:
• Give each operation $x=2$ received amount
• Assign push to cost 1 dollar
• Assign pop to cost 1 dollar
• Multi pop to cost $n$ dollar for number of elements popped Proving invariant:
• Initially: $amount=0$, $size=0$
• Push:
  • Assume $amount\ge size$ before push
  • Then, $amoun{t}^{\prime }=amount+credit(push)-cost(push)$
  • $⟹amoun{t}^{\prime }=amount+2-1=amount+1$
  • $siz{e}^{\prime }=size+1$
  • Then, invariant holds as $amoun{t}^{\prime }\ge siz{e}^{\prime }$
• Pop:
  • Assume $amount\ge size$ before pop
  • Then, $amoun{t}^{\prime }=amount+credit(pop)-cost(pop)$
  • $⟹amoun{t}^{\prime }=amount+1$
  • $siz{e}^{\prime }=size+1$
  • Then, invariant holds as $amoun{t}^{\prime }\ge siz{e}^{\prime }$
• Multi-pop:
  • Assume $amount>size$ before multipop
  • Let $n$ be number of items popped
  • Then, $amoun{t}^{\prime }=credit(\text{multipop})-cost(\text{multipop})$
  • $=amount+2-n$
  • $siz{e}^{\prime }=size-n$
  • Thus, $amoun{t}^{\prime }\ge size;$
• Finally, note that $size\ge 0⟹amount\ge 0$ is an invariant