Amortized algorithm analysis: making sense of the Accounting Method
The idea
It’s called the accounting method because we want to get a feel of how expensive an algorithm is, on average.
The idea is that expensive operations will happen rarely enough so that if we over-estimate cheap operation, this over-estimation will compensate the cost of the expensive ones.
Worst case
Say $C_{exp}$ is the cost of an expensive operation and $C_{cheap}$ is the cost of a cheap one. Worst case analysis for the algorithm would mean setting $C_{cheap} = C_{exp}$.
Amortization
But we know that not all operation as as expensive as the most expensive so overestimating $C_{cheap}$ and underestimating $C_{exp}$ will give us an overall cost that will be larger than the actual cost but smaller than the worst case cost:
Averaging the cost of cheap and expensive operations together, along the whole run of the algorithm is called amortization
Example
Theory
Take inserting in an array as a toy example. If the array is full, we need to double its size: you have to create a new, larger array and copy all existing elements inside it. Assigning an element (in a large enough array) on the other hand is cheap: you just have to assign a value to a location in the array.
So the array is initially empty
| Iteration | Insert | Array | Size | Cost of operation | Credit for operation | Credit left |
|---|---|---|---|---|---|---|
| 0 | null | [_] | 1 | 0 | 0 | 0 |
| 1 | 1 | [1] | 1 | 1 | $c$ | c-1 |
| 2 | 2 | [1, 2] | 2 | 1 + 1 | $c$ | (c - 1) + c - 2 |
| 3 | 3 | [1,2, 3, _] | 4 | 2 + 1 | $c$ | (2c - 3) + c - 3 |
| 4 | 4 | [1,2,3,4] | 4 | 1 | $c$ | (3c - 6) + c - 1 |
We always want to have credit left for later as we want to over-estimate (but not too much) the overall cost of the algorithm. In other words, we can set $c$ to 100 and we’ll be sure to have a loooot of credits left. But we want the smallest $c$ such that we never go bankrupt, that is to say the tightest bound.
Application
So how do we chose $c$?
- One could see that if $c=3$ then we’re good in the column Credit Left (iteration 2 would fail with $c=2$).
- Another way to put it is to realize that each element will be paid for in two occasions:
- once it is added to the array
- once when it is copied into a new, larger array
- if $c=2$, the first time the table expands, all good, the item pays $2$ for both its insertion and copy. But what about the next copy?
- Subsequent copies would not be paid for so we need subsequent items to pay for this!
- if $c=3$ each item pays for its insertion, its copy and the copy of a previous item.
- it is guaranteed that it will be enough since we double the size of each array: when we need to copy, there are as many new elements as there were “old” element from the previous growth
So here what it’d look like:
| Iteration | Insert | Array | Size | Cost of operation | Credit for operation | Credit left |
|---|---|---|---|---|---|---|
| 0 | null | [_] | 1 | 0 | 0 | 0 |
| 1 | 1 | [1] | 1 | 1 | 3 | 2 |
| 2 | 2 | [1, 2] | 2 | 1 + 1 | 3 | 3 |
| 3 | 3 | [1,2, 3, _] | 4 | 2 + 1 | 3 | 3 |
| 4 | 4 | [1,2,3,4] | 4 | 1 | 3 | 5 |
| 5 | 5 | [1, 3, 3, 4, 5, _, _, _] | 8 | 4 + 1 | 3 | 3 |
| 6 | 6 | [1, 3, 3, 4, 5, 6, _, _] | 8 | 1 | 3 | 5 |
| 7 | 7 | [1, 3, 3, 4, 5, 6, 7, _] | 8 | 1 | 3 | 7 |
| 8 | 8 | [1, 3, 3, 4, 5, 6, 7, 8] | 8 | 1 | 3 | 9 |
| 9 | 9 | [1, 3, 3, 4, 5, 6, 7, 8, 9, _, …] | 16 | 8 + 1 | 3 | 3 |
How do elements pay for the copy of previous ones? (click to expand)
Leyt’s look at iteration 9:
- it has a cost of 9: copying the 8 previous elements, and adding 9 in the new, expanded array
- Items $5..8$ have assign one of their 3 credits to
- their copy at next expansion
- their insertion
- and saved for the copy of elements $1..4$ at next expansion
This is why we need amortized analysis: the sequence $insert(5),..,insert(8)$ as a whole pays for the one, expensive subsequent expansion
Amortized cost
So what is the final amortizated complexity of inserting in a resizable array? It is $O(1)$ as the cost never grows: each credit is spent exactly (except for the first one as there is no resize, could be even tighter to assign it a special credit of 1).