## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required Chapter 5
Amortized analysis
In this chapter, we brieﬂy discuss amortized analysis, the goal of which is to
average the cost of n successive operations. This should not be confused with
the average cost of an operation. We ﬁrst describe the three classical methods
with examples (Section 5.1) and then proceed with exercises in Section 5.2,
with solutions in Section 5.3.
5.1 Methods for amortized analysis
First, we introduce two examples to illustrate the methods used to conduct an
amortized analysis. Then, we present the three classical methods: aggregate
analysis, the accounting method, and the potential method.
5.1.1 Running examples
The ﬁrst example is a k-bit counter that we want to increment. Initially, the
counter has a value of 0, and each operation increments it. Formally, this
counter is represented by an array A of k bits, where A[i] is the (i + 1)-th
bit, for 0 i k 1. A number x represented by this counter is such that
x =
k1
i=0
A[i].2
i
. For instance, if k = 6 and if we perform n = 4 operations,
we obtain the following sequence:
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 1 0
0 0 0 0 1 1
0 0 0 1 0 0
The cost of an increment is deﬁned as the number of bits that should be
modiﬁed. This cost i s not constant f or each value of the counter; it is equal
to the number of successive 1s at the right of the counter, plus 1 (switching
the ﬁrst 0 to 1).
The second example consists of inserting n elements in a table, dynamically,
starting from an empty table. We insert a new element directly in the table if
105
© 2014 by Taylor & Francis Group, LLC 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+
n
2
+
n
4
+···
2n, regardless of the value of k. This leads to an amortized cost per operation
of 2.
For the table insertion, for any integer k 0, the cost of the (2
k
+ 1)-th
insertion is c(i) = 2
k
+ 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
have:
n
i=1
c(n) n +
log
2
(n)
k=0
2
k
3n
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
operation.
For the k-bit counter, each time we ﬂip a bit from 0 to 1, we decide to pay
2 euros
1
: 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
1
Yes, \$2 would be okay, too.
© 2014 by Taylor & Francis Group, LLC

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required