Amortized ComplexityPotential FunctionPotential Function ExampleAccounting MethodAccounting Method ExampleSlide 6Potential MethodPotential Method Exampleith Symbol Is Not ) or ;ith Symbol Is )ith Symbol Is ;Binary CounterWorst-Case MethodAggregate MethodSlide 15Slide 162nd Increment.3rd Increment.4th Increment.Slide 20Slide 21Slide 22Amortized ComplexityAggregate method.•Accounting method.•Potential function method.Potential Function•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 Examplea = x + ( ( a + b ) * c + d ) + y ;actual costamortized costpotential1 1 1 1 1 11 1 1 5 1 1 1 1 7 1 1 72 2 2 2 2 22 2 2 2 2 2 2 2 2 2 2 21 2 3 4 5 67 8 9 6 7 8 9105 6 7 2Potential = stack size except at end.Accounting Method•Guess the amortized cost.•Show that P(n) – P(0) >= 0.Accounting Method Example•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. create an empty stack; for (int i = 1; i <= n; i++) // n is number of symbols in statement processNextSymbol();Accounting Method Example•Potential >= number of symbols on stack.•Therefore, P(i) >= 0 for all i.•In particular, P(n) >= 0.a = x + ( ( a + b ) * c + d ) + y ;actual costamortized costpotential1 1 1 1 1 11 1 1 5 1 1 1 1 7 1 1 72 2 2 2 2 22 2 2 2 2 2 2 2 2 2 2 21 2 3 4 5 67 8 9 6 7 8 9105 6 7 2Potential 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(i–1) = amortized cost – actual cost•amortized cost = actual cost + PPotential Method Example•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. create an empty stack; for (int i = 1; i <= n; i++) // n is number of symbols in statement processNextSymbol();ith Symbol Is Not ) or ;•Actual cost of processNextSymbol is 1.•Number of elements on stack increases by 1.-P = P(i) – P(i–1) = 1.•amortized cost = actual cost + P = 1 + 1 = 2ith Symbol Is )•Actual cost of processNextSymbol is #unstacked + 1.•Number of elements on stack decreases by #unstacked –1.-P = P(i) – P(i–1) = 1 – #unstacked.•amortized cost = actual cost + P = #unstacked + 1 + (1 – #unstacked) = 2ith Symbol Is ;•Actual cost of processNextSymbol is #unstacked = P(n–1).•Number of elements on stack decreases by P(n–1).-P = P(n) – P(n–1) = 2 – P(n–1).•amortized cost = actual cost + P = P(n–1) + (2 – P(n–1)) = 2Binary 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•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.counter0 0 0 0 0Aggregate Method•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.counter0 0 0 0 0Accounting 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.bitscredits000 0 0 00 0 0 0000 0 0 10 0 0 12nd Increment. 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 0bitscredits000 0 0 10 0 0 1000 0 1 00 0 1 03rd 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 1 changes from 1 to 0bitscredits000 0 1 00 0 1 0000 0 1 10 0 1 14th Increment. 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 bitsbitscredits000 0 1 10 0 1 1000 1 0 00 1 0 0Accounting 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 >= 0Potential 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(i–1) = amortized cost – actual cost•amortized cost = actual cost + PPotential 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) =