Amortized Analysis

Introduction:

In

amortized analysis we calculate average time over sequence of data structure

over all operation which is performed in analysis. Amortized analysis always

show average cost minimum but in case if nested operation are performed then

amortized perform expensive. Amortized analysis is totally different from

average case analysis. This analysis ensure that average progress of each function

fall into worst case.

In

this paper we will discuss three types of techniques which are used in

amortized analysis. First is Aggregate

analysis second is Accounting method

and last is Potential method. We

will use two types of examples for explaining these techniques like MULTILOP and Binary counter.

Aggregate Analysis:

Aggregate analysis define that for

all n input values a sequence of operation performed and it take total time in

worst case time T(n). On this worst case time we will perform amortized

analysis and then average case time will be T(n)/n. It is compulsory to perform

amortized analysis on each operation even there are different type of operation

in a sequence we have to perform aggregate analysis on each operation.

Stack operation:

In

this example we analyze the stack that is augmented with a new operation. Here

explain two fundamental operation, each has O(1) time.

PUSH (S.x) Pushes object x into Stack

S

POP(S) pop the top object and return

it. On empty stack calling pop generate an error.

Since there is time given for each

operation which is 1. So each PUSH and POP operation take time 1 if there are n

PUSH and POP operation then it take (n) time.

From above example calling it return

(a) state from above picture. Then the top four objects are displayed by

calling this MULTIPOP(S, 4) show result in (b) from above picture. Then it will

empty the stack by calling MULTIPOP(S, 7) show in (c) from above picture.

We analyze that total time will be 1

for each PUSH POP function. Every time of calling While function POP and PUSH

produce a single time call and total cost of MULTIPOP is min(S, k). Let we

analyze that n POP and PUSH calls and MULTIPOP operations on an empty stack.

This will produce O (n) worst case

time on MULTIPOP operation in sequence. Hence sequence of n operation will cost

O (n2).

Now using aggregate analysis we can

get better upper bound then this. On every call of MULTIPOP there is a single

execution of POP and PUSH function and it will be worst case if there are n

inputs. In aggregate analysis total cost of an operation O(n)/n=O(1). Here cost

of all operation will be O(1) and here worst case bound will be O(n) by

amortize analysis on n operations.

Increment a binary counter:

Here another example of aggregate

analysis let a binary counter that implement k-bit binary counter that count

upward from zero. We use an array A 0….k-1 of bit where k-1.Initialy stored

variable x is zero and counter having A0 is starting and Ak-1 is ending

index.

If above figure an 8bit counter run

from 0 to 16 by above increment operation. Those bits that are flip to achieve

next value are highlighted. The running cost of flipping shows in right. You

can see that total cost will always less than twice the total numbers of

INCREMENT operations. The total number of INCREMENT sequence are

The worst case time of sequence of

all increment operations is O (n). So average cost of amortized will be O (n)/n=O

(1).

The Counting Method:

In

accounting method we assign different charges to every different operation,

some operations charged along with less or more cost which they actually have.

We called this charges on operation amortized

cost. When amortized cost of any operation exceeded from original cost we

assign an object in data structure as credit.

By this method we can check the cost of every operation either exceeding or

nothing change happen. We also called this as deposit or used up. This method

is different from amortized analysis, which have same cost for all operations.

We have to take carefully amortized cost if we take average case time by using

aggregate method we have to ensure that that cost will provide upper bound on

total cost of operation. Denote cost of ith operation by ci and

amortized cost of ith operation by ci^.

For all sequence of n operations. Total credit cost that

stores in data structure is less that or between amortized or actual cost.

Stack Operation:

Let

recall the previous stack operation’s cost

PUSH 1,

POP 1,

MULTIPOP min (k, s)

Here k is argument passed to MULTIPOP

and s is size of stack when this function is called. Let us assigning the

amortized cost.

PUSH 2,

POP 0,

MULTIPOP 0,

Here amortized cost of each

operations are zero but actual cost is some value here amortized cost can be

same and different from each other even asymptotically. Now we take example of

plates using stack and use one dollar as a cost for push and pay to credit, the

plate into the stack. On multipop we have to pay off credit from pop plates. In

other word for pop we have to pay one dollar to credit so that pop value always

will be non-negative number of plates and we ensure that stack value will be

non-negative. So n operation of PUSH POP and MULTIPOP will amortized cost will

be upper bound O (n).

Incrementing binary counter:

In accounting method we assume a

increment operation binary counter start from zero. We have observed earlier

that cost is proportional to total bit flipped. Let we use dollar bill example

in this example. For example in amortized analysis we use 2 dollar for set a

bit to 1. When a bit flipped it will cost 1 bit and kept other dollar for bit

flipped from zero to one. At any point there is one dollar on a counter to

credit on, So we have nothing to do to reset a bit we just have to pay just one

dollar bill on the bit. Thus for n operations there is only O(n) amortized cost

which bounds the actual cost.

Potential Method:

In

accounting method we use credit for prepaid work but in potential we use just

“Potential Energy” or just “Potential” for future use pay work operations. We

use potential with hole in data structure rather than specifying object in data

structure.

Potential method working:

·

n

total operations

·

D0

initial data structure

·

Di

actual cost of ith operations

·

Di-1 after applying operation

·

? (Di) Potential method representation

·

ci^

Amortized cost

w.r.t ith operation represent

·

? (D0)=0 and ?(Di )>0 for all i

·

?(Di )

– ?(Di-1)=? ?ci >0

then Ci Ci I store work is data structure for future use

·

? ?i<0 then Ci < Ci^ store
work for pay future
The amortized cost of each function is
therefore its actual cost plus the change in potential due to operation.
Stack Operation:
We define a potential function ? that is total
objects in stack. For empty stack Do we start ? (Do) =0
this number in stack can never negative and ith operation have non-negative
potential energy thus
Sine amortized cost of these
operations is O(1) and for n operations cost will be O(n). Since we have
already say that ? (Di)>= ? (Do) total cost is upper

bound to actual cost. Worst case of n operation is O(n).