 ## Aggregate Method ### Aggregate Method Characteristics

• It computes the worst case time T(n) for a sequence of n operations.
• The amortized cost is T(n)/n per operation.
• It gives the average performance of each operation in the worst case.
• This method is less precise than other methods, as all operations are assigned the same cost.

Application 1: Stack operations

In the following pseudocode, the operation STACK-EMPTY returns TRUE if there are no object currently on the stack, and FALSE otherwise.

MULTIPOP(s, k)
while (.NOT. STACK-EMPTY(s) and k ≠ 0)
do    pop(s)
k = k-1

Analysis

1. Worst-case cost for MULTIPOP is O(n). There are n successive calls to MULTIPOP would cost O(n2). We get unfair cost O(n2) because each item can be poped only once for each time it is pushed.

2. In a sequence of n mixed operations the most times multipop can be called n/2.Since the cost of push and pop is O(1), the cost of n stack operations is O(n). Therefore, amortized cost of an operation is the average: O(n)/n = O(1).

Application 2: Binary Counter

We use an array A[0 . . k-1] of bits, where length [A] = k, as the counter. A binary number x that is stored in the counter has its lowest-order bit in A and its highest-order bit is A[k-1], so that   k-1Si=0 2iA[i]. Initially, x = 0, and thus A[i] = 0 for i=0, 1, . . . , k-1.
To add 1 (modulus 2k ) to the value in the counter, use the following pseudocode.

INCREMENT (A)
i = 0
while i < length [A] and A[i] = 1
do A[i] = 0
i = i+1
if i < length [A]
then A[i] = 1

A single execution of  INCREMENT takes O(k) in worst case when Array A contains all 1's. Thus, a sequence of n INCREMENT operation on an initially zero counter takes O(nk) in the worst case. This bound is correct but not tight.

Amortized Analysis

We can tighten the analysis to get a worst-case cost for a sequence of an INCREMENT's by observing that not all bits flip each time INCREMENT is called.

Bit A is changed ceiling n times (every time)
Bit A is changed ceiling [n/21] times (every other time)
Bit A is changed ceiling [n/22] times (every other time)
.
.
.
Bit A is changed ceiling [n/2i] times.

In general, for i = 0, 1, . . ., lg n , bit A[i] flips n/2i times in a sequence of n INCREMENT operations on an initially zero counter.
For i > lg(n) , bit A i never flips at all. The total number of flips in a sequence is thus

floor(log)Si=0 n/2i < n Si=0  1/2i  = 2n

Therefore, the worst-case time for a sequence of n INCREMENT operation on an initially zero counter is therefore O(n), so the amortized cost of each operation is O(n)/n = O(1). 