AMORTIZEDANALYSIS OF A BINARY COUNTER Thereare two types of Binary Counter:1. Aggregate Method2.
Accounting Method3. Potential Method Accounting Method: Ø Accounting method in aamortized analysis is a method which is based on accounting.Ø It is the easiest way tocalculate the amortized cost of an operation.
Ø It is better than theaggregate method or potential method.Ø But this method do notgive us a guarantee of obvious analysis.Ø This Method does notinclude any complexity.Ø Each operation in thismethod is assigned with a amortized costØ The actual cost should begreater than the amortized cost.Ø Different amortized costs beingassigned to multiple different amortized operations.
Some working containamortized cost more or less than the actual cost.Ø When the cost exceeds fromthe actual cost of amortized operation. Then the specific objects is assignedwith a difference in a data structure called credit.
Ø If the amortized cost isless than the actual cost, then the credit is used to pay for those operations.Ø Overall amortized cost ofoperations should be >= overall actual cost <> total credit should be>= 0.Ø The credit in theamortized analysis is linked with a data structure. · The accounting method itself includes two operations:1. Stack Operation 2.
Binary Operation STACKOPERATION: The stack operation consists of three operations:1. Push2. Pop3. Multi-pops § To learn the countingmethod of amortized analysis , here is the example:Actual Costs: Push 1,Pop 1,Multi pop min (a, p) where a is argument given to the multi pop and p is size of a stackNow, the assigned amortized costPush 2,Pop 0,Multi pop 0, Now we can see that , the amortized cost of multi pop is 0whereas the actual cost was a variable , so the overall amortized cost of threeoperation is O(1). But the overallcost of amortized operation is O(n).But sometimes the amortized cost can be changeasymptotically.
Binary Counter Increment:The binary counter with the increment operation starts withzero. The running time of increment operation is directly proportional to theno.of bits flipped.
Example:Let us take an example of a Dollar bill to present each unit of cost. For amortized analysis , let charge anamortized cost of 2 dollars to set it to a 1 dollar. If the bit is set , wewill take 1 dollar out 2 dollars to pay actual bit , then we place the left bitas a credit. At the anyother time we can use that left 1 dollar , and our bitwill never reset to zero. We will just pay for the dollar reset bill.
Thus thenumber of 1’s in the counter can never be negative neither the amount of creditcan be negative. So for “n” increment operators the amount of total amortized costis O(n), in which actual cost is bound.