Amortized Analysis
Used to find the amortized cost: worst-case (not probabilistic) bound for a sequence of n operations, per operation.
Three ways to calculate amortized cost:
1. aggregate analysis: find the average cost per operation
2. accounting: assign extra cost to some operations to cover other operations, sum up the costs
3. potential method: construct a potential formula and find the total cost
Why are we studying this? Because it gives us insight into how an algorithm behaves, and helps us find a tight worst-case bound.
1. Aggregate analysis
Example1: multipop stack
MULTIPOP(S, k) //pop k items from stack S
while !empty(S) and k!=0
POP(S)
k--
Operation / Actual cost for one operation / Worst cost for n operationsPUSH(S, x) / O(1) / 1
POP(S) / O(1) / 1
MULTIPOP(S, k) / min(S.size, k) / n
If we push n elements, then we can pop n elements max. So, for any value of n, any sequence of PUSH, POP, MULTIPOP can take maximum of O(n) time. The average is O(n)/n.
Example 2: binary counter
INCREMENT(A)
k = length(A)
i = 0
while i < k and A[i] ==1
A[i] = 0
i++
if i < k
A[i] = 1
Ex: 8-bit counter
00000000
00000001
00000010
00000011
00000100
00000101
00000110
….
Lose worst bound: one pass through INCREMENT takes theta(k) time at worst. So, n passes takes theta(nk).
Tight worst bound: one pass through INCREMENT flips bits in various frequency: LSB is always flipped, next higher bit is flipped every other time, etc. In general, bit at position i flips floor(n/2^i) times in a sequence of n INCREMENT operations on an initially zero counter.
Total worst cost = SUM[i=0, k-1] (floor(n/2^i))
< SUM[i=0, infinity] ((n/2^i))
= n* SUM[i=0, infinity] (1/2^i) (A.6)
= 2n
= O(n)
2. The accounting method
Each operation is assigned an accounting cost, but has to pay the actual cost. Some operation leave “extra payment” for the next operation. Since accounting cost is the amortized cost, it has to be larger than the actual cost, so the extra payment is always positive.
Example1: multipop stack
Operation / Actual cost for one operation / Accounting costPUSH(S, x) / 1 / 2
POP(S) / 1 / 0
MULTIPOP(S, k) / min(S.size, k) / 0
Every time we do a PUSH, we give 2$, out of which we have to use 1$ to pay the actual cost, and we and leave 1$ for the POP. Every POP does not use any accounting money, and pays itself with the dollar left from PUSH.
So the total worst cost for n operations is O(n).
Example 2: binary counter
Operation / Actual cost for one operation / Accounting costFlip bit to 1 / 1 / 2
Flip bit to 0 / 1 / 0
If we start with empty counter: every time we INCREMENT, we pay only 2$ to flip to 1. Then every 1 will have 1$ on it to flip it back to 0. So, sequence of n INCREMENTS will cost 2n, i.e. O(n).
Example: dynamic tables
TABLE-INSERT(T, x)
if size(T) = 0
allocate table(T) with 1 slot
size(T) = 1
if num(T) = size(T)
allocate new_table with 2*size(T) slots
insert all items in table(T) into new_table
free table(T)
table(T) = new_table
size(T) = 2*size(T)
insert x into table(T)
num(T)++
Tracing it:
Table size: 0 1 2 4 8 16
i: 1 2 3 4 5 6 7 8 9
ci: 1 2 3 1 1 1 1 1 9 …
ci: Cost of ith insert.
Aggregate analysis:
ci = i if (i-1) is an exact power of 2
1 otherwise
SUM[i=1, n] ci = 1 + 2 + 3 + 1 + 1 + 1 + 1+ 1 + 9 + ….
<= n + SUM[j=0, floor(lgn)] 2^j
< n+ 2n
= 3n
= O(n)
Accounting method:
Operation / Actual cost for one operation / Accounting costAdd new item to table / 1 / 3
Move the new item to new table when necessary / 1 / 0
Move an item before “our” new item to new table / 1 / 0
E.g. if the table has m slots and m/2 elements, i.e. after an expansion: when we add a new item, then we must copy all previous m items to the new table. 3$ pays 1$ for the new item, and leaves 1$ on it and 1$ on another item already in the table. Every time we insert, we do this, so by the time we are ready to expand the table, each item in the table has 1$ on it and can move to the new table.