Java Reference
In-Depth Information
14.3
Amortized Analysis
This section presents the concept of amortized analysis, which is the analysis for
a series of operations taken as a whole. In particular, amortized analysis allows us
to deal with the situation where the worst-case cost for n operations is less than
n times the worst-case cost of any one operation. Rather than focusing on the indi-
vidual cost of each operation independently and summing them, amortized analysis
looks at the cost of the entire series and “charges” each individual operation with a
share of the total cost.
We can apply the technique of amortized analysis in the case of a series of se-
quential searches in an unsorted array. For n random searches, the average-case
cost for each search is n=2, and so the expected total cost for the series is n
2
=2.
Unfortunately, in the worst case all of the searches would be to the last item in the
array. In this case, each search costs n for a total worst-case cost of n
2
. Compare
this to the cost for a series of n searches such that each item in the array is searched
for precisely once. In this situation, some of the searches must be expensive, but
also some searches must be cheap. The total number of searches, in the best, av-
erage, and worst case, for this problem must be
P
i=i
i n
2
=2. This is a factor
of two better than the more pessimistic analysis that charges each operation in the
series with its worst-case cost.
As another example of amortized analysis, consider the process of increment-
ing a binary counter. The algorithm is to move from the lower-order (rightmost)
bit toward the high-order (leftmost) bit, changing 1s to 0s until the first 0 is en-
countered. This 0 is changed to a 1, and the increment operation is done. Below is
Java code to implement the increment operation, assuming that a binary number of
length n is stored in array
A
of length n.
for(i=0;((i<A.length)&&(A[i]==1));i++)
A[i]=0;
if(i<A.length)
A[i]=1;
If we count from 0 through 2
n
1, (requiring a counter with at least n bits),
what is the average cost for an increment operation in terms of the number of bits
processed? Naive worst-case analysis says that if all n bits are 1 (except for the
high-order bit), then n bits need to be processed. Thus, if there are 2
n
increments,
then the cost is n2
n
. However, this is much too high, because it is rare for so many
bits to be processed. In fact, half of the time the low-order bit is 0, and so only
that bit is processed. One quarter of the time, the low-order two bits are 01, and
so only the low-order two bits are processed. Another way to view this is that the
low-order bit is always flipped, the bit to its left is flipped half the time, the next
bit one quarter of the time, and so on. We can capture this with the summation
