Home | | Programming and Data Structure II | Aggregate Analysis

Chapter: Programming and Data structures : Advanced Non-Linear Data Structures

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[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/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 |


Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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