Algorithms

Lecture 9: Amortized Analysis [Fa’13]

The goode workes that men don whil they ben in good lifal amortised by synne folwyng.
— Geoffrey Chaucer, “The Persones [Parson’s] Tale” (c.1400)
I will gladly pay you Tuesday for a hamburger today.
— J. Wellington Wimpy, “Thimble Theatre” (1931)
I want my two dollars!
— Johnny Gasparini [Demian Slade], “Better Off Dead” (1985)
A dollar here, a dollar there. Over time, it adds up to two dollars.
— Jarod Kintz, The Titanic Would Never Have Sunk
if It Were Made out of a Sink (2012)9

Amortized Analysis

9.1

Incrementing a Binary Counter

It is a straightforward exercise in induction, which often appears on Homework 0, to prove thatany non-negative integer n can be represented as the sum of distinct powers of 2. Although somestudents correctly use induction on the number of bits—pulling off either the least significant bitor the most significant bit in the binary representation and letting the Recursion Fairy convert
the remainder—the most commonly submitted proof uses induction on the value of the integer,
as follows:
Proof: The base case n = 0 is trivial. For any n > 0, the inductive hypothesis implies that there
is set of distinct powers of 2 whose sum is n − 1. If we add 20 to this set, we obtain a multiset of
powers of two whose sum is n, which might contain two copies of 20 . Then as long as there are
two copies of any 2i in the multiset, we remove them both and insert 2i+1 in their place. The
sum of the elements of the multiset is unchanged by this replacement, because 2i+1 = 2i + 2i .
Each iteration decreases the size of the multiset by 1, so the replacement process must eventuallyterminate. When it does terminate, we have a set of distinct powers of 2 whose sum is n.
This proof is describing an algorithm to increment a binary counter from n − 1 to n. Here’s amore formal (and shorter!) description of the algorithm to add 1 to a binary counter. The input B
is an (infinite) array of bits, where B[i] = 1 if and only if 2i appears in the sum.
Increment(B[0 .. ∞]):
i←0
while B[i] = 1
B[i] ← 0i ← i+1
B[i] ← 1

We’ve already argued that Increment must terminate, but how quickly? Obviously, therunning time depends on the array of bits passed as input. If the first k bits are all 1s, thenIncrement takes Θ(k) time. The binary representation of any positive integer n is exactly
blg nc + 1 bits long. Thus, if B represents an integer between 0 and n, Increment takes Θ(log n)time in the worst case.
© Copyright 2018 Jeff Erickson.
This work is licensed under a Creative Commons License (http://creativecommons.org/licenses/by-nc-sa/4.0/).
Free distribution is strongly encouraged; commercial distribution is expressly forbidden.
See http://jeffe.cs.illinois.edu/teaching/algorithms/ for the most recent revision.

1

Algorithms

9.2

Lecture 9: Amortized Analysis [Fa’13]

Counting from 0 to n

Now suppose we call Increment n times, starting with a zero counter. How long does it taketo count from 0 to n? If we only use the worst-case running time for each Increment, we getan upper bound of O(n log n) on the total running time. Although this bound is correct, we cando better; in fact, the total running time is only Θ(n). This section describes several general
methods for deriving, or at least proving, this linear time bound. Many (perhaps even all) of
these methods are logically equivalent, but different formulations are more natural for different
problems.
9.2.1

Summation

Perhaps the simplest way to derive a tighter bound is to observe that Increment doesn’t flip
Θ(log n) bits every time it is called. The least significant bit B[0] does flip in every iteration, but
B[1] only flips every other iteration, B[2] flips every 4th iteration, and in general, B[i] flips every
2i th iteration. Because we start with an array full of 0’s, a sequence of n Increments flips each
bit B[i] exactly bn/2i c times. Thus, the total number of bit-flips for the entire sequence is
blg
nc j
X
i=0

∞
nk X n
= 2n.
<
2i
2i
i=0

(More precisely, the number of flips is exactly 2n − #1(n), where #1(n) is the number of 1 bitsin the binary representation of n.) Thus, on average, each call to Increment flips just less than
two bits, and therefore runs in constant time.
This sense of “on average” is quite different from the averaging we consider with randomized
algorithms. There is no probability involved; we are averaging over a sequence of operations, notthe possible running times of a single operation. This averaging idea is called amortization—theamortized time for each Increment is O(1). Amortization is a sleazy clever trick used byaccountants to average large one-time costs over long periods of time; the most common example
is calculating uniform payments for a loan, even though the borrower is paying interest on lessand less capital over time. For this reason, it is common to use “cost” as a synonym for running
time in the context of amortized analysis. Thus, the worst-case cost of Increment is O(log n),
but the amortized cost is only O(1).
Most textbooks call this particular technique “the aggregate method”, or “aggregate analysis”,
but these are just fancy names for computing the total cost of all operations and then dividing by
the number of operations.
The Summation Method. Let T (n) be the worst-case running time for a sequenceof n operations. The amortized time for each operation is T (n)/n.
9.2.2

TaxationA second method we can use to derive amortized bounds is called either the accounting methodor the taxation method. Suppose it costs us a dollar to toggle a bit, so we can measure therunning time of our algorithm in dollars. Time is money!
Instead of paying for each bit flip when it happens, the Increment Revenue Service charges a
two-dollar increment tax whenever we want to set a bit from zero to one. One of those dollars is
spent changing the bit from zero to one; the other is stored away as credit until we need to reset
the same bit to zero. The key point here is that we always have enough credit saved up to pay for2

Algorithms

Lecture 9: Amortized Analysis [Fa’13]

the next Increment. The amortized cost of an Increment is the total tax it incurs, which isexactly 2 dollars, since each Increment changes just one bit from 0 to 1.
It is often useful to distribute the tax income to specific pieces of the data structure. For
example, for each Increment, we could store one of the two dollars on the single bit that is set
for 0 to 1, so that that bit can pay to reset itself back to zero later on.
Taxation Method 1. Certain steps in the algorithm charge you taxes, so that the
total cost incurred by the algorithm is never more than the total tax you pay. The
amortized cost of an operation is the overall tax charged to you during that operation.
A different way to schedule the taxes is for every bit to charge us a tax at every operation,
regardless of whether the bit changes of not. Specifically, each bit B[i] charges a tax ofP1/2i dollars
for each Increment. The total tax we are charged during each Increment is i≥0 2−i = 2
dollars. Every time a bit B[i] actually needs to be flipped, it has collected exactly $1, which isjust enough for us to pay for the flip.
Taxation Method 2. Certain portions of the data structure charge you taxes at each
operation, so that the total cost of maintaining the data structure is never more than
the total taxes you pay. The amortized cost of an operation is the overall tax you
pay during that operation.
In both of the taxation methods, our task as algorithm analysts is to come up with anappropriate ‘tax schedule’. Different ‘schedules’ can result in different amortized time bounds.
The tightest bounds are obtained from tax schedules that just barely stay in the black.
9.2.3

Charging

Another common method of amortized analysis involves charging the cost of some steps to someother, earlier steps. The method is similar to taxation, except that we focus on where each unit oftax is (or will be) spent, rather than where is it collected. By charging the cost of some operations
to earlier operations, we are overestimating the total cost of any sequence of operations, since we
pay for some charges from future operations that may never actually occur.
The Charging Method. Charge the cost of some steps of the algorithm to earlier
steps, or to steps in some earlier operation. The amortized cost of the algorithm
is its actual running time, minus its total charges to past operations, plus its total
charge from future operations.
For example, in our binary counter, suppose we charge the cost of clearing a bit (changing
its value from 1 to 0) to the previous operation that sets that bit (changing its value from 0 to1). If we flip k bits during an Increment, we charge k − 1 of those bit-flips to earlier bit-flips.
Conversely, the single operation that sets a bit receives at most one unit of charge from the nexttime that bit is cleared. So instead of paying for k bit-flips, we pay for at most two: one for
actually setting a bit, plus at most one charge from the future for clearing that same bit. Thus,
the total amortized cost of the Increment is at most two bit-flips.
We can visualize this charging scheme as follows. For each integer i, we represent the running
time of the ith Increment as a stack of blocks, one for each bit flip. The jth block in the ith
stack is white if the ith Increment changes B[ j] from 0 to 1, and shaded if the ith Incrementchanges B[ j] from 1 to 0. If we moved each shaded block onto the white block directly to its left,
there would at most two blocks in each stack.
3

Algorithms

1

2

3

Lecture 9: Amortized Analysis [Fa’13]

4

5

6

7

8

9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

Charging scheme for a binary counter.

9.2.4

Potential

The most powerful method (and the hardest to use) builds on a physics metaphor of ‘potential
energy’. Instead of associating costs or taxes with particular operations or pieces of the data
structure, we represent prepaid work as potential that can be spent on later operations. The
potential is a function of the entire data structure.
Let Di denote our data structure after i operations have been performed, and let Φi denote
its potential. Let ci denote the actual cost of the ith operation (which changes Di−1 into Di ).
Then the amortized cost of the ith operation, denoted ai , is defined to be the actual cost plus theincrease in potential:
ai = ci + Φi − Φi−1
So the total amortized cost of n operations is the actual total cost plus the total increase inpotential:
n
n
n
X
X
X
ai =
(ci + Φi − Φi−1 ) =c i + Φ n − Φ0 .
i=1

i=1

i=1

A potential function is valid if Φi − Φ0 ≥ 0 for all i. If the potential function is valid, then the
total actual cost of any sequence of operations is always less than the total amortized cost:
n
X
i=1

ci =

n
X

ai − Φn ≤

i=1

n
X

ai .

i=1

For our binary counter example, we can define the potential Φi after the ith Increment tobe the number of bits with value 1. Initially, all bits are equal to zero, so Φ0 = 0, and clearly
Φi > 0 for all i > 0, so this is a valid potential function. We can describe both the actual cost ofan Increment and the change in potential in terms of the number of bits set to 1 and reset to 0.
ci = #bits changed from 0 to 1 + #bits changed from 1 to 0
Φi − Φi−1 = #bits changed from 0 to 1 − #bits changed from 1 to 0
Thus, the amortized cost of the ith Increment is
ai = ci + Φi − Φi−1 = 2 × #bits changed from 0 to 1
Since Increment changes only one bit from 0 to 1, the amortized cost Increment is 2.
The Potential Method. Define a potential function for the data structure that is
initially equal to zero and is always non-negative. The amortized cost of an operation
is its actual cost plus the change in potential.

4

Algorithms

Lecture 9: Amortized Analysis [Fa’13]

For this particular example, the potential is precisely the total unspent taxes paid using thetaxation method, so it should be no surprise that we obtain precisely the same amortized cost.
In general, however, there may be no natural way to interpret change in potential as “taxes” or“charges”. Taxation and charging are useful when there is a convenient way to distribute costs tospecific steps in the algorithm or components of the data structure. Potential arguments allow us
to argue more globally when a local distribution is difficult or impossible.
Different potential functions can lead to different amortized time bounds. The trick to using
the potential method is to come up with the best possible potential function. A good potentialfunction goes up a little during any cheap/fast operation, and goes down a lot during any
expensive/slow operation. Unfortunately, there is no general technique for finding good potentialfunctions, except to play around with the data structure and try lots of possibilities (most ofwhich won’t work).

9.3

Incrementing and Decrementing

Now suppose we wanted a binary counter that we can both increment and decrement efficiently.
A standard binary counter won’t work, even in an amortized sense; if we alternate between 2k
and 2k − 1, every operation costs Θ(k) time.
A nice alternative is represent each integer as a pair (P, N ) of bit strings, subject to theinvariant P ∧ N = 0 where ∧ represents bit-wise And. In other words,
For every index i, at most one of the bits P[i] and N [i] is equal to 1.
If we interpret P and N as binary numbers, the actual value of the counter is P − N ; thus,
intuitively, P represents the “positive” part of the pair, and N represents the “negative” part.
Unlike the standard binary representation, this new representation is not unique, except for zero,
which can only be represented by the pair (0, 0). In fact, every positive or negative integer canbe represented has an infinite number of distinct representations.
We can increment and decrement our double binary counter as follows. Intuitively, theIncrement algorithm increments P, and the Decrement algorithm increments N ; however, inboth cases, we must change the increment algorithm slightly to maintain the invariant P ∧ N = 0.
Increment(P, N ):i←0while P[i] = 1
P[i] ← 0i ← i+1

Decrement(P, N ):i←0while N [i] = 1
N [i] ← 0i ← i+1

if N [i] = 1
N [i] ← 0else
P[i] ← 1

if P[i] = 1
P[i] ← 0else
N [i] ← 1

P = 10001
P = 10010
P = 10011
P = 10000
P = 10000
P = 10000
P = 10001
++
++
++
−−
−−
++
N = 01100 −→ N = 01100 −→ N = 01100 −→ N = 01000 −→ N = 01001 −→ N = 01010 −→ N = 01010
P−N =5P−N =6P−N =7P−N =8P−N =7P−N =6P−N =7
Incrementing and decrementing a double-binary counter.

Now suppose we start from (0, 0) and apply a sequence of n Increments and Decrements.
In the worst case, each operation takes Θ(log n) time, but what is the amortized cost? We can’t
5

Algorithms

Lecture 9: Amortized Analysis [Fa’13]

use the aggregate method here, because we don’t know what the sequence of operations looks
like.
What about taxation? It’s not hard to prove (by induction, of course) that after either P[i]or N [i] is set to 1, there must be at least 2i operations, either Increments or Decrements,
before that bit is reset to 0. So if each bit P[i] and N [i] pays a tax of 2−i at each operation, we
will always have enoughto pay for the next operation. Thus, the amortized cost of each
P money−i
operation is at most i≥0 2 · 2 = 4.
We can get even better amortized time bounds using the potential method. Define thepotential Φi to be the number of 1-bits in both P and N after i operations. Just as before, we haveci = #bits changed from 0 to 1 + #bits changed from 1 to 0
Φi − Φi−1 = #bits changed from 0 to 1 − #bits changed from 1 to 0=⇒

ai = 2 × #bits changed from 0 to 1

Since each operation changes at most one bit to 1, the ith operation has amortized cost ai ≤ 2.
?

9.4

Gray Codes

An attractive alternate solution to the increment/decrement problem was independently suggested
by several students. Gray codes (named after Frank Gray, who discovered them in the 1950s) aremethods for representing numbers as bit strings so that successive numbers differ by only one bit.
For example, here is the four-bit binary reflected Gray code for the integers 0 through 15:0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000
The general rule for incrementing a binary reflected Gray code is to invert the bit that would be
set from 0 to 1 by a normal binary counter. In terms of bit-flips, this is the perfect solution; eachincrement of decrement by definition changes only one bit. Unfortunately, the naïve algorithm tofind the single bit to flip still requires Θ(log n) time in the worst case. Thus, so the total costof maintaining a Gray code, using the obvious algorithm, is the same as that of maintaining anormal binary counter.
Fortunately, this is only true of the naïve algorithm. The following algorithm, discoveredby Gideon Ehrlich1 in 1973, maintains a Gray code counter in constant worst-case time perincrement! The algorithm uses a separate ‘focus’ array F [0 .. n] in addition to a Gray-code bit
array G[0 .. n − 1].
EhrlichGrayIncrement(n):j ← F [0]F [0] ← 0
if j = nG[n − 1] ← 1 − G[n − 1]else
G[ j] = 1 − G[ j]F [ j] ← F [ j + 1]
F [ j + 1] ← j + 1

EhrlichGrayInit(n):for i ← 0 to n − 1
G[i] ← 0
for i ← 0 to n
F [i] ← i

1Gideon Ehrlich. Loopless algorithms for generating permutations, combinations, and other combinatorialconfigurations. J. Assoc. Comput. Mach. 20:500–513, 1973.

6

Algorithms

Lecture 9: Amortized Analysis [Fa’13]

The EhrlichGrayIncrement algorithm obviously runs in O(1) time, even in the worst case.
Here’s the algorithm in action with n = 4. The first line is the Gray bit-vector G, and the secondline shows the focus vector F , both in reverse order:
G : 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000
F : 3210, 3211, 3220, 3212, 3310, 3311, 3230, 3213, 4210, 4211, 4220, 4212, 3410, 3411, 3240, 3214
Voodoo! I won’t explain in detail how Ehrlich’s algorithm works, except to point out the following
invariant. Let B[i] denote the ith bit in the standard binary representation of the current number.
If B[ j ] = 0 and B[ j − 1] = 1, then F [ j ] is the smallest integer k > j such that B[k] = 1;otherwise, F [ j] = j. Got that?
But wait — this algorithm only handles increments; what if we also want to decrement?
Sorry, I don’t have a clue. Extra credit, anyone?

9.5

Generalities and Warnings

Although computer scientists usually apply amortized analysis to understand the efficiency ofmaintaining and querying data structures, you should remember that amortization can be applied
to any sequence of numbers. Banks have been using amortization to calculate fixed payments forinterest-bearing loans for centuries. The IRS allows taxpayers to amortize business expenses orgambling losses across several years for purposes of computing income taxes. Some cell phone
contracts let you to apply amortization to calling time, by rolling unused minutes from one month
into the next month.
It’s also important to remember that amortized time bounds are not unique. For a data
structure that supports multiple operations, different amortization schemes can assign different
costs to exactly the same algorithms. For example, consider a generic data structure that can be
modified by three algorithms: Fold, Spindle, and Mutilate. One amortization scheme might
imply that Fold and Spindle each run in O(log n) amortized time, while Mutilate runs in O(n)pamortized time. Another scheme might imply that Fold runs in O( n) amortized time, while
Spindle and Mutilate each run in O(1) amortized time. These two results are not necessarily
inconsistent! Moreover, there is no general reason to prefer one of these sets of amortized timebounds over the other; our preference may depend on the context in which the data structure is
used.

Exercises
1. Suppose we are maintaining a data structure under a series of n operations. Let f (k)denote the actual running time of the kth operation. For each of the following functions f ,determine the resulting amortized cost of a single operation. (For practice, try all of themethods described in this note.)(a) f (k) is the largest integer i such that 2i divides k.
(b) f (k) is the largest power of 2 that divides k.
(c) f (k) = n if k is a power of 2, and f (k) = 1 otherwise.
(d) f (k) = n2 if k is a power of 2, and f (k) = 1 otherwise.
(e) f (k) is the index of the largest Fibonacci number that divides k.
(f) f (k) is the largest Fibonacci number that divides k.
7

Algorithms

Lecture 9: Amortized Analysis [Fa’13](g) f (k) = k if k is a Fibonacci number, and f (k) = 1 otherwise.
(h) f (k) = k2 if k is a Fibonacci number, and f (k) = 1 otherwise.
(i) f (k) is the largest integer whose square divides k.
(j) f (k) is the largest perfect square that divides k.
(k) f (k) = k if k is a perfect square, and f (k) = 1 otherwise.
(l) f (k) = k2 if k is a perfect square, and f (k) = 1 otherwise.
(m) Let T be a complete binary search tree, storing the integer keys 1 through n. f (k) is
the number of ancestors of node k.
(n) Let T be a complete binary search tree, storing the integer keys 1 through n. f (k) is
the number of descendants of node k.
(o) Let T be a complete binary search tree, storing the integer keys 1 through n. f (k) is
the square of the number of ancestors of node k.
(p) Let T be a complete binary search tree, storing the integer keys 1 through n. f (k) =size(k) lg size(k), where size(k) is the number of descendants of node k.
(q) Let T be an arbitrary binary search tree, storing the integer keys 0 through n. f (k) is
the length of the path in T from node k − 1 to node k.
(r) Let T be an arbitrary binary search tree, storing the integer keys 0 through n. f (k) is
the square of the length of the path in T from node k − 1 to node k.
(s) Let T be a complete binary search tree, storing the integer keys 0 through n. f (k) is
the square of the length of the path in T from node k − 1 to node k.
2. Consider the following modification of the standard algorithm for incrementing a binary
counter.
Increment(B[0 .. ∞]):
i←0
while B[i] = 1
B[i] ← 0i ← i+1
B[i] ← 1
SomethingElse(i)The only difference from the standard algorithm is the function call at the end, to a
black-box subroutine called SomethingElse.
Suppose we call Increment n times, starting with a counter with value 0. The amortized
time of each Increment clearly depends on the running time of SomethingElse. Let
T (i) denote the worst-case running time of SomethingElse(i). For example, we provedin class that Increment algorithm runs in O(1) amortized time when T (i) = 0.
(a) What is the amortized time per Increment if T (i) = 42?
(b) What is the amortized time per Increment if T (i) = 2i ?
(c) What is the amortized time per Increment if T (i) = 4i ?
p i(d) What is the amortized time per Increment if T (i) = 2 ?
(e) What is the amortized time per Increment if T (i) = 2i /(i + 1)?
8

Algorithms

Lecture 9: Amortized Analysis [Fa’13]

3. An extendable array is a data structure that stores a sequence of items and supports thefollowing operations.
• AddToFront(x) adds x to the beginning of the sequence.
• AddToEnd(x) adds x to the end of the sequence.
• Lookup(k) returns the kth item in the sequence, or Null if the current length of thesequence is less than k.
Describe a simple data structure that implements an extendable array. Your AddToFront
and AddToBack algorithms should take O(1) amortized time, and your Lookup algorithm
should take O(1) worst-case time. The data structure should use O(n) space, where n is
the current length of the sequence.
4. An ordered stack is a data structure that stores a sequence of items and supports thefollowing operations.
• OrderedPush(x) removes all items smaller than x from the beginning of thesequence and then adds x to the beginning of the sequence.
• Pop deletes and returns the first item in the sequence (or Null if the sequence isempty).
Suppose we implement an ordered stack with a simple linked list, using the obvious
OrderedPush and Pop algorithms. Prove that if we start with an empty data structure,
the amortized cost of each OrderedPush or Pop operation is O(1).
5. A multistack consists of an infinite series of stacks S0 , S1 , S2 , . . . , where the ith stack Si canhold up to 3i elements. The user always pushes and pops elements from the smallest stack
S0 . However, before any element can be pushed onto any full stack Si , we first pop all theelements off Si and push them onto stack Si+1 to make room. (Thus, if Si+1 is already full,
we first recursively move all its members to Si+2 .) Similarly, before any element can bepopped from any empty stack Si , we first pop 3i elements from Si+1 and push them onto
Si to make room. (Thus, if Si+1 is already empty, we first recursively fill it by popping
elements from Si+2 .) Moving a single element from one stack to another takes O(1) time.
Here is pseudocode for the multistack operations MSPush and MSPop. The internal
stacks are managed with the subroutines Push and Pop.
MPush(x) :i←0while Si is fulli ← i+1

MPop(x) :i←0while Si is emptyi ← i+1

while i > 0i ← i−1for j ← 1 to 3i
Push(Si+1 , Pop(Si ))while i > 0i ← i−1for j ← 1 to 3i
Push(Si , Pop(Si+1 ))Push(S0 , x)

return Pop(S0 )(a) In the worst case, how long does it take to push one more element onto a multistack
containing n elements?
9

Algorithms

Lecture 9: Amortized Analysis [Fa’13]×9×3

Making room in a multistack, just before pushing on a new element.

(b) Prove that if the user never pops anything from the multistack, the amortized costof a push operation is O(log n), where n is the maximum number of elements in themultistack during its lifetime.
(c) Prove that in any intermixed sequence of pushes and pops, each push or pop operation
takes O(log n) amortized time, where n is the maximum number of elements in themultistack during its lifetime.
6. Recall that a standard (FIFO) queue maintains a sequence of items subject to the following
operations.
• Push(x): Add item x to the end of the sequence.
• Pull(): Remove and return the item at the beginning of the sequence.
It is easy to implement a queue using a doubly-linked list and a counter, so that the entire
data structure uses O(n) space (where n is the number of items in the queue) and theworst-case time per operation is O(1).
(a) Now suppose we want to support the following operation instead of Pull:• MultiPull(k): Remove the first k items from the front of the queue, and return
the kth item removed.
Suppose we use the obvious algorithm to implement MultiPull:
MultiPull(k):for i ← 1 to kx ← Pull()
return x

Prove that in any intermixed sequence of Push and MultiPull operations, theamortized cost of each operation is O(1)(b) Now suppose we also want to support the following operation instead of Push:• MultiPush(x, k): Insert k copies of x into the back of the queue.
Suppose we use the obvious algorithm to implement MultiPuush:MultiPush(k, x):
for i ← 1 to k
Push(x)10

Algorithms

Lecture 9: Amortized Analysis [Fa’13]

Prove that for any integers ` and n, there is a sequence of ` MultiPush and MultiPulloperations that require Ω(n`) time, where n is the maximum number of items in thequeue at any time. Such a sequence implies that the amortized cost of each operationis Ω(n).
(c) Describe a data structure that supports arbitrary intermixed sequences of MultiPushand MultiPull operations in O(1) amortized cost per operation. Like a standard
queue, your data structure should use only O(1) space per item.
7. Recall that a standard (FIFO) queue maintains a sequence of items subject to the following
operations.
• Push(x): Add item x to the end of the sequence.
• Pull(): Remove and return the item at the beginning of the sequence.
• Size(): Return the current number of items in the sequence.
It is easy to implement a queue using a doubly-linked list, so that it uses O(n) space (where
n is the number of items in the queue) and the worst-case time for each of these operations
is O(1).
Consider the following new operation, which removes every tenth element from thequeue, starting at the beginning, in Θ(n) worst-case time.
Decimate():n ← Size()
for i ← 0 to n − 1
if i mod 10 = 0
Pull() 〈〈result discarded〉〉else
Push(Pull())

Prove that in any intermixed sequence of Push, Pull, and Decimate operations, theamortized cost of each operation is O(1).
8. Chicago has many tall buildings, but only some of them have a clear view of Lake Michigan.
Suppose we are given an array A[1 .. n] that stores the height of n buildings on a city block,indexed from west to east. Building i has a good view of Lake Michigan if and only if every
building to the east of i is shorter than i.
Here is an algorithm that computes which buildings have a good view of Lake Michigan.
What is the running time of this algorithm?
GoodView(A[1 .. n]):initialize a stack S
for i ← 1 to n
while (S not empty and A[i] > A[Top(S)])
Pop(S)
Push(S, i)
return S

11

Algorithms

Lecture 9: Amortized Analysis [Fa’13]

9. Suppose we can insert or delete an element into a hash table in O(1) time. In order toensure that our hash table is always big enough, without wasting a lot of memory, we will
use the following global rebuilding rules:• After an insertion, if the table is more than 3/4 full, we allocate a new table twice as
big as our current table, insert everything into the new table, and then free the oldtable.
• After a deletion, if the table is less than 1/4 full, we allocate a new table half as big as
our current table, insert everything into the new table, and then free the old table.
Show that for any sequence of insertions and deletions, the amortized time per operationis still O(1). [Hint: Do not use potential functions.]
10. Professor Pisano insists that the size of any hash table used in his class must always be a
Fibonacci number. He insists on the following variant of the previous global rebuilding
strategy. Suppose the current hash table has size Fk .
• After an insertion, if the number of items in the table is Fk−1 , we allocate a new hashtable of size Fk+1 , insert everything into the new table, and then free the old table.
• After a deletion, if the number of items in the table is Fk−3 , we allocate a new hashtable of size Fk−1 , insert everything into the new table, and then free the old table.
Show that for any sequence of insertions and deletions, the amortized time per operationis still O(1). [Hint: Do not use potential functions.]
11. Remember the difference between stacks and queues? Good.
(a) Describe how to implement a queue using two stacks and O(1) additional memory,so that the amortized time for any enqueue or dequeue operation is O(1). The only
access you have to the stacks is through the standard subroutines Push and Pop.
(b) A quack is a data structure combining properties of both stacks and queues. It canbe viewed as a list of elements written left to right such that three operations are
possible:• QuackPush(x): add a new item x to the left end of the list;• QuackPop(): remove and return the item on the left end of the list;• QuackPull(): remove the item on the right end of the list.
Implement a quack using three stacks and O(1) additional memory, so that theamortized time for any QuackPush, QuackPop, or QuackPull operation is O(1).
In particular, each element in the quack must be stored in exactly one of the threestacks. Again, you cannot access the component stacks except through the interfacefunctions Push and Pop.
12. Let’s glom a whole bunch of earlier problems together. Yay! An random-access doubleended multi-queue or radmuque (pronounced “rad muck”) stores a sequence of items andsupports the following operations.
• MultiPush(x, k) adds k copies of item x to the beginning of the sequence.
12

Algorithms

Lecture 9: Amortized Analysis [Fa’13]• MultiPoke(x, k) adds k copies of item x to the end of the sequence.
• MultiPop(k) removes k items from the beginning of the sequence and retrns the lastitem removed. (If there are less than k items in the sequence, remove them all andreturn Null.)• MultiPull(k) removes k items from the end of the sequence and retrns the last item
removed. (If there are less than k items in the sequence, remove them all and return
Null.)• Lookup(k) returns the kth item in the sequence. (If there are less than k items in thesequence, return Null.)
Describe and analyze a simple data structure that supports these operations using O(n)space, where n is the current number of items in the sequence. Lookup should run in O(1)worst-case time; all other operations should run in O(1) amortized time.
13. Suppose you are faced with an infinite number of counters x i , one for each integer i.
Each counter stores an integer mod m, where m is a fixed global constant. All counters
are initially zero. The following operation increments a single counter x i ; however, if x ioverflows (that is, wraps around from m to 0), the adjacent counters x i−1 and x i+1 areincremented recursively.
Nudgem (i):xi ← xi + 1
while x i ≥ m
xi ← xi − m
Nudgem (i − 1)
Nudgem (i + 1)(a) Prove that Nudge3 runs in O(1) amortized time. [Hint: Prove that Nudge3 always
halts!](b) What is the worst-case total time for n calls to Nudge2 , if all counters are initiallyzero?
14. Now suppose you are faced with an infinite two-dimensional grid of modular counters,
one counter x i, j for every pair of integers (i, j). Again, all counters are initially zero. The
counters are modified by the following operation, where m is a fixed global constant:
2dNudgem (i, j):x i, j ← x i + 1
while x i, j ≥ m
x i, j ← x i, j − m
2dNudgem (i − 1, j)
2dNudgem (i, j + 1)
2dNudgem (i + 1, j)
2dNudgem (i, j − 1)(a) Prove that 2dNudge5 runs in O(1) amortized time.
Æ(b) Prove or disprove: 2dNudge4 also runs in O(1) amortized time.
13

Algorithms

ÆLecture 9: Amortized Analysis [Fa’13](c) Prove or disprove: 2dNudge3 always halts.

? 15.

Suppose instead of powers of two, we represent integers as the sum of Fibonacci numbers.
In other words, instead of an array of bits, we keep an array of fits, where the ith leastsignificant fit indicates whether the sum includes the ith Fibonacci number Fi . For example,
the fitstring 101110 F represents the number F6 + F4 + F3 + F2 = 8+3+2+1 = 14. Describe
algorithms to increment and decrement a single fitstring in constant amortized time. [Hint:
Most numbers can be represented by more than one fitstring!]? 16.

A doubly lazy binary counter represents any number as a weighted sum of powers of two,
where each weight is one of four values: −1, 0, 1, or 2. (For succinctness, I’ll write 1 insteadof −1.) Every integer—positive, negative, or zero—has an infinite number of doubly lazybinary representations. For example, the number 13 can be represented as 1101 (thestandard binary representation), or 2101 (because 2 · 23 − 22 + 20 = 13) or 10111 (because
24 − 22 + 21 − 20 = 13) or 11200010111 (because −210 + 29 + 2 · 28 + 24 − 22 + 21 − 20 = 13).
To increment a doubly lazy binary counter, we add 1 to the least significant bit, thencarry the rightmost 2 (if any). To decrement, we subtract 1 from the lest significant bit,and then borrow the rightmost 1 (if any).
LazyIncrement(B[0 .. n]):B[0] ← B[0] + 1
for i ← 1 to n − 1
if B[i] = 2
B[i] ← 0
B[i + 1] ← B[i + 1] + 1
returnLazyDecrement(B[0 .. n]):B[0] ← B[0] − 1
for i ← 1 to n − 1
if B[i] = −1
B[i] ← 1
B[i + 1] ← B[i + 1] − 1
returnFor example, here is a doubly lazy binary count from zero up to twenty and then backdown to zero. The bits are written with the least significant bit B[0] on the right, omitting
all leading 0’s.
++

++

++

++

++

++

++

++

++

++

0 −→ 1 −→ 10 −→ 11 −→ 20 −→ 101 −→ 110 −→ 111 −→ 120 −→ 201 −→ 210
++

++

++

++

++

++

++

++

++

−−

−−

−−

−−

−−

−−

−−

−−

−−

−−

−−

−−

−−

−−

−−

−−

++

−→ 1011 −→ 1020 −→ 1101 −→ 1110 −→ 1111 −→ 1120 −→ 1201 −→ 1210 −→ 2011 −→ 2020−−−→ 2011 −→ 2010 −→ 2001 −→ 2000 −→ 2011 −→ 2110 −→ 2101 −→ 1100 −→ 1111 −→ 1010
−−

−−

−−

−→ 1001 −→ 1000 −→ 1011 −→ 1110 −→ 1101 −→ 100 −→ 111 −→ 10 −→ 1 −→ 0

Prove that for any intermixed sequence of increments and decrements of a doubly lazybinary number, starting with 0, the amortized time for each operation is O(1). Do notassume, as in the example above, that all the increments come before all the decrements.

© Copyright 2018 Jeff Erickson.
This work is licensed under a Creative Commons License (http://creativecommons.org/licenses/by-nc-sa/4.0/).
Free distribution is strongly encouraged; commercial distribution is expressly forbidden.
See http://jeffe.cs.illinois.edu/teaching/algorithms for the most recent revision.

14