Amortized Complexity Aggregate method. Accounting method. Potential function method. Potential Function P() P(i) = amortizedCost(i) actualCost(i) + P(i 1) (P(i) P(i 1)) = (amortizedCost(i) actualCost(i)) P(n) P(0) = (amortizedCost(i) actualCost(i)) P(n) P(0) >= 0

When P(0) = 0, P(i) is the amount by which the first i operations have been over charged. Potential Function Example a=x+((a+b actual cost 1 1 1 1 1 11 1 1 amortized cost 2 2 2 2 2 22 2 2 potential 1 2 3 4 5 67 8 9 )*c+d )+y; 511117117

222222222 6 7 8 9 10 5 6 7 2 Potential = stack size except at end. Accounting Method Guess the amortized cost. Show that P(n) P(0) >= 0. Accounting Method Example create an empty stack;

for (int i = 1; i <= n; i++) // n is number of symbols in statement processNextSymbol(); Guess that amortized complexity of processNextSymbol is 2. Start with P(0) = 0. Can show that P(i) >= number of elements on stack after ith symbol is processed. Accounting Method Example a=x+((a+b

actual cost 1 1 1 1 1 11 1 1 amortized cost 2 2 2 2 2 22 2 2 potential 1 2 3 4 5 67 8 9 )*c+d )+y; 511117117 222222222 6 7 8 9 10 5 6 7 2 Potential >= number of symbols on stack. Therefore, P(i) >= 0 for all i.

In particular, P(n) >= 0. Potential Method Guess a suitable potential function for which P(n) P(0) >= 0 for all n. Derive amortized cost of ith operation using P = P(i) P(i1) = amortized cost actual cost amortized cost = actual cost + P Potential Method Example

create an empty stack; for (int i = 1; i <= n; i++) // n is number of symbols in statement processNextSymbol(); Guess that the potential function is P(i) = number of elements on stack after ith symbol is processed (exception is P(n) = 2). P(0) = 0 and P(i) P(0) >= 0 for all i. ith Symbol Is Not ) or ; Actual cost of processNextSymbol is 1.

Number of elements on stack increases by 1. P = P(i) P(i1) = 1. amortized cost = actual cost + P =1+1=2 ith Symbol Is ) Actual cost of processNextSymbol is #unstacked + 1. Number of elements on stack decreases by #unstacked 1. P = P(i) P(i1) = 1 #unstacked.

amortized cost = actual cost + P = #unstacked + 1 + (1 #unstacked) =2 ith Symbol Is ; Actual cost of processNextSymbol is #unstacked = P(n1). Number of elements on stack decreases by P(n1). P = P(n) P(n1) = 2 P(n1).

amortized cost = actual cost + P = P(n1) + (2 P(n1)) =2 Binary Counter n-bit counter Cost of incrementing counter is number of bits that change. Cost of 001011 => 001100 is 3. Counter starts at 0. What is the cost of incrementing the counter

m times? Worst-Case Method Worst-case cost of an increment is n. Cost of 011111 => 100000 is 6. So, the cost of m increments is at most mn. Aggregate Method 00000 counter Each increment changes bit 0 (i.e., the right

most bit). Exactly floor(m/2) increments change bit 1 (i.e., second bit from right). Exactly floor(m/4) increments change bit 2. Aggregate Method 00000 counter Exactly floor(m/8) increments change bit 3. So, the cost of m increments is m + floor(m/2) + floor(m/4) + .... < 2m

Amortized cost of an increment is 2m/m = 2. Accounting Method Guess that the amortized cost of an increment is 2. Now show that P(m) P(0) >= 0 for all m. 1st increment: one unit of amortized cost is used to pay for the change in bit 0 from 0 to 1. the other unit remains as a credit on bit 0 and is used later to pay for the time when bit 0 changes from 1 to 0.

bits credits 00000 00000 00001 00001 2nd Increment. bits

credits 00001 00001 00010 00010 one unit of amortized cost is used to pay for the change in bit 1 from 0 to 1 the other unit remains as a credit on bit 1 and is used

later to pay for the time when bit 1 changes from 1 to 0 the change in bit 0 from 1 to 0 is paid for by the credit on bit 0 3rd Increment. bits credits 00010 00010

00011 00011 one unit of amortized cost is used to pay for the change in bit 0 from 0 to 1 the other unit remains as a credit on bit 0 and is used later to pay for the time when bit 1 changes from 1 to 0 4th Increment.

bits credits 00011 00011 00100 00100 one unit of amortized cost is used to pay for the change in bit 2 from 0 to 1

the other unit remains as a credit on bit 2 and is used later to pay for the time when bit 2 changes from 1 to 0 the change in bits 0 and 1 from 1 to 0 is paid for by the credits on these bits Accounting Method P(m) P(0) = (amortizedCost(i) actualCost(i)) = amount by which the first m increments have been over charged = number of credits

= number of 1s in binary rep. of m >= 0 Potential Method Guess a suitable potential function for which P(n) P(0) >= 0 for all n. Derive amortized cost of ith operation using P = P(i) P(i1) = amortized cost actual cost amortized cost = actual cost + P

Potential Method Guess P(i) = number of 1s in counter after ith increment. P(i) >= 0 and P(0) = 0. Let q = # of 1s at right end of counter just before ith increment (01001111 => q = 4). Actual cost of ith increment is 1+q. P = P(i) P(i 1) = 1 q (0100111 => 0101000) amortized cost = actual cost + P = 1+q + (1 q) = 2