## 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**

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

- 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-1}**S**_{i=0
}2^{i}*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^{1}] times
(every other time)

Bit *A*[0] is changed ceiling [*n*/2^{2}] times
(every other time)

.

.

.

Bit *A*[0] is changed ceiling [*n*/2^{i}]
times.

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