O'Reilly logo

A Guide to Algorithm Design by Frédéric Vivien, Yves Robert, Anne Benoit

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

No credit card required

Chapter 5
Amortized analysis
In this chapter, we briefly 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 first 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 first 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 defined as the number of bits that should be
modified. 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 first 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 first 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 flips each time, the second one flips 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 first 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 flip a bit from 0 to 1, we decide to pay
2 euros
1
: 1 euro for the flip and another one so that we will be able to flip
back the bit from 1 to 0 without having to pay. For this example, since at
each increment there is only one bit to flip 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.

Start Free Trial

No credit card required