Accounting method

The accounting method is one of the main methods used in amortised analysis of algorithms. The core principle is simple:

• For an operation $f(x)$ and a sequence of inputs $(x_1,x_2,\dots ,x_n)$.
• Let $c(x_i)$ be the actual cost of $f(x_i)$ and $\hat{c}$ be the amortised cost for $f(x_i)$.
• Then, for each input, we assign a credit, where ${\hat{c}}_i-c_i$ is the leftover credit after executing operation $i$. We require that ${\sum }_{i=1}^n({\hat{c}}_i-c_i)\ge 0\forall n$.
  • If $c_k\le {\hat{c}}_k$, i.e., the amortised cost is more, we can execute the operation. Then, we store the difference as “credit” to be used for later operations.
  • If $c_k>{\hat{c}}_k$, the actual cost is more. In this case, we use the credit that we’ve built up to execute the operation. Even if the difference ${\hat{c}}_i-c_i<0$, we can still use the credit to ensure the summation is non-negative.
    • If the summation is non-negative, then the guess for $\hat{c}$ is wrong.

Another aspect of our proof is the credit invariant. We make a claim about the value of the cumulative stored credit ${\sum }_{i=1}^n({\hat{c}}_i-c_i)$. Usually it looks something like “element with property $P$ contains $x$ stored credit ($x$ can be dependent on property $P$)“.

Then, if we show that the credit invariant always maintains positive stored credit, i.e., ${\sum }_{i=1}^n({\hat{c}}_i-c_i)\ge 0$ for all $n$, then each operation $i$ is $\mathcal{O}({\hat{c}}_i)$ amortised.