AMORTIZED

ANALYSIS OF A BINARY COUNTER

There

are two types of Binary Counter:

1. Aggregate Method

2. Accounting Method

3. Potential Method

Accounting Method:

Ø Accounting method in a

amortized analysis is a method which is based on accounting.

Ø It is the easiest way to

calculate the amortized cost of an operation.

Ø It is better than the

aggregate method or potential method.

Ø But this method do not

give us a guarantee of obvious analysis.

Ø This Method does not

include any complexity.

Ø Each operation in this

method is assigned with a amortized cost

Ø The actual cost should be

greater than the amortized cost.

Ø Different amortized costs being

assigned to multiple different amortized operations. Some working contain

amortized cost more or less than the actual cost.

Ø When the cost exceeds from

the actual cost of amortized operation. Then the specific objects is assigned

with a difference in a data structure called credit.

Ø If the amortized cost is

less than the actual cost, then the credit is used to pay for those operations.

Ø Overall amortized cost of

operations should be >= overall actual cost <> total credit should be

>= 0.

Ø The credit in the

amortized analysis is linked with a data structure.

·

The accounting method itself includes two operations:

1. Stack Operation

2. Binary Operation

STACK

OPERATION: The stack operation consists of three operations:

1.

Push

2.

Pop

3.

Multi-pops

§ To learn the counting

method 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 stack

Now, the assigned amortized cost

Push 2,

Pop 0,

Multi pop 0,

Now we can see that , the amortized cost of multi pop is 0

whereas the actual cost was a variable , so the overall amortized cost of three

operation is O(1). But the overall

cost of amortized operation is O(n).

But sometimes the amortized cost can be change

asymptotically.

Binary Counter Increment:

The binary counter with the increment operation starts with

zero. The running time of increment operation is directly proportional to the

no.of bits flipped.

Example:

Let us take an example of a Dollar bill to present each unit of cost.

For amortized analysis , let charge an

amortized cost of 2 dollars to set it to a 1 dollar. If the bit is set , we

will take 1 dollar out 2 dollars to pay actual bit , then we place the left bit

as a credit. At the anyother time we can use that left 1 dollar , and our bit

will never reset to zero. We will just pay for the dollar reset bill. Thus the

number of 1’s in the counter can never be negative neither the amount of credit

can be negative. So for “n” increment operators the amount of total amortized cost

is O(n), in which actual cost is bound.