106 Chapter 5. Amortized analysis
there is space, with a cost 1. Otherwise, we create a new table that has twice
the size of the original table (or a table of size 1 for the ﬁrst insertion); we
copy the content of the original table and insert the new element. The cost
is then the size of the original table plus 1. Note that the table is always at
least half full (an empty table is considered full), so even if the cost may be
high for some operations, we then have free space for the next operations.
For both examples, the amortized analysis consists of asking the following
question: What is the cost of n successive operations?
5.1.2 Aggregate analysis
The goal of this method is to show that the cost of n successive operations
can be bounded by T (n). Therefore, in the worst case, the cost per operation
on average, i.e., the amortized cost per operation, is bounded by T (n)/n.
For the k-bit counter, it is obvious that th e cost of n successive increment
operations is bounded by nk. However, this upper bound can be improved.
Indeed, the right-most bit ﬂips each time, the second one ﬂips every second
time, and so on. Therefore, the cost of n operations is at most n+
2n, regardless of the value of k. This leads to an amortized cost per operation
For the table insertion, for any integer k 0, the cost of the (2
insertion is c(i) = 2
+ 1, i.e., the size of the table is doubled. Otherwise, the
cost is c(i) = 1 (including the cost of the ﬁrst insertion, c( 1) ). Therefore, we
c(n) n +
and an amortized cost of 3.
5.1.3 Accounting method
The principle of this method is to p ay in advance for costly operations that
may happen afterwards, hence, keeping a constant cost per operation. One has
to guarantee that at the time of operation i, one has enough credit (including
advance payment and the payment for the operation) to cover the cost of the
For the k-bit counter, each time we ﬂip a bit from 0 to 1, we decide to pay
: 1 euro for the ﬂip and another one so that we will be able to ﬂip
back the bit from 1 to 0 without having to pay. For this example, since at
each increment there is only one bit to ﬂip from 0 to 1, the cost is 2 at each
Yes, $2 would be okay, too.
© 2014 by Taylor & Francis Group, LLC