Java Reference
In-Depth Information
(charging costs to bits going from right to left)
n
X
1
2
i
< 2:
i=0
In other words, the average number of bits flipped on each increment is 2, leading
to a total cost of only 2 2
n
for a series of 2
n
increments.
A useful concept for amortized analysis is illustrated by a simple variation on
the stack data structure, where the
pop
function is slightly modified to take a sec-
ond parameter k indicating that k pop operations are to be performed. This revised
pop function, called
multipop
, might look as follows:
/
**
popkelementsfromstack
*
/
voidmultipop(intk);
The “local” worst-case analysis for
multipop
is (n) for n elements in the
stack. Thus, if there are m
1
calls to
push
and m
2
calls to
multipop
, then the
naive worst-case cost for the series of operation is m
1
+ m
2
n = m
1
+ m
2
m
1
.
This analysis is unreasonably pessimistic. Clearly it is not really possible to pop
m
1
elements each time
multipop
is called. Analysis that focuses on single op-
erations cannot deal with this global limit, and so we turn to amortized analysis to
model the entire series of operations.
The key to an amortized analysis of this problem lies in the concept of poten-
tial. At any given time, a certain number of items may be on the stack. The cost for
multipop
can be no more than this number of items. Each call to
push
places
another item on the stack, which can be removed by only a single
multipop
op-
eration. Thus, each call to
push
raises the potential of the stack by one item. The
sum of costs for all calls to
multipop
can never be more than the total potential of
the stack (aside from a constant time cost associated with each call to
multipop
itself).
The amortized cost for any series of
push
and
multipop
operations is the
sum of three costs. First, each of the
push
operations takes constant time. Second,
each
multipop
operation takes a constant time in overhead, regardless of the
number of items popped on that call. Finally, we count the sum of the potentials
expended by all
multipop
operations, which is at most m
1
, the number of
push
operations. This total cost can therefore be expressed as
m
1
+ (m
2
+ m
1
) = (m
1
+ m
2
):
A similar argument was used in our analysis for the partition function in the
Quicksort algorithm (Section 7.5). While on any given pass through the while
loop the left or right pointers might move all the way through the remainder of the
