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[0]
flips every time, total *n* times.

A[1]
flips every other time, Ã«*n*/2Ã» times.

A[2]
flips every forth time, Ã«*n*/4Ã» times.

â€¦.

for *i*=0,1,â€¦,*k*-1, A[*i*] flips Ã«*n*/2* ^{i}*Ã» 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 |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.