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(n²). We get unfair cost O(n²) 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[0] and its highest-order bit is A[k-1], so that   ^k-1S_i=0 2ⁱA[i]. Initially, x = 0, and thus A[i] = 0 for i=0, 1, . . . , k-1.
To add 1 (modulus 2^k ) 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[0] is changed ceiling n times (every time)
Bit A[0] is changed ceiling [n/2¹] times (every other time)
Bit A[0] is changed ceiling [n/2²] times (every other time)
        .
        .
        .
Bit A[0] is changed ceiling [n/2ⁱ] times.

In general, for i = 0, 1, . . ., lg n, bit A[i] flips n/2ⁱ 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)S_i=0  n/2ⁱ < n ^∞S_i=0  1/2ⁱ  = 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).