Home | | Programming and Data Structure II | Aggregate Analysis

# Aggregate Analysis

In fact, a sequence of n operations on an initially empty stack cost at most O(n).

AGGREGATE ANALYSIS:

Â·        In fact, a sequence of n operations on an initially empty stack cost at most O(n).

Â·        Each object can be POP only once (including in MULTIPOP) for each time it is PUSHed. #POPs is at most #PUSHs, which is at most n.

Â·        Thus the average cost of an operation is O(n)/n = O(1).

Â·        Amortized cost in aggregate analysis is defined to be average cost.

Example: Increasing a binary counter

Binary counter of length k, A[0..k-1] of bit array.

INCREMENT(A)

1.     i < --- 0

2.     while i<k and A[i]=1

3.       do A[i] < --- 0 (flip, reset)

4.                               i < --- i+1

5.     if i<k

6.  then A[i] < ---  1  (flip, set)

Amortized (Aggregate) Analysis of INCREMENT (A)

The running time determined by #flips but not all bits flip each time INCREMENT is called.

A flips every time, total n times.

A flips every other time, Ă«n/2Ă» times.

A flips every forth time, Ă«n/4Ă» times.

â€¦.

for i=0,1,â€¦,k-1, A[i] flips  Ă«n/2iĂ» times.

Thus total #flips is  â€˘         Thus the worst case running time is O(n) for a sequence of n INCREMENTs.

â€˘         So the amortized cost per operation is O(1).

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Programming and Data structures : Advanced Non-Linear Data Structures : Aggregate Analysis |