By

1. The idea
2. Example
3. Resources

# 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).