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 =

k−1

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

Start Free Trial

No credit card required