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.
  • Note: if something costs $0,itis$\mathcal O(1)$,not$\mathcal O(0)$.Thus,ifwedoa0-costoperation$k$times,thenithasacostof$\mathcal O(k)$.

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.

Note that we don’t need to exactly reach 0 at the end of the day (when the structure is empty or something). We can charge more than we need, and use less credit than we have. This maintains the invariant without ever reaching 0.