Amortized analysis
------------------
-- definition and motivation
-- example of counting
-- example of implementing a FIFO queue with two stacks
-- example of doubling-array for stack.
-- potential functions
Amortized analysis means analyzing time-averaged cost for a
sequence of operations.
Motivation is that traditional worst-case-per-operation
analysis can give overly pessimistic bound if the only way
of having an expensive operation is to have a lot of cheap
ones before it.
NOTE: this is DIFFERENT from our usual notion of "average
case analysis" -- we're not making any assumptions about
inputs being chosen at random -- we're just averaging over
time.
The approach is going to be to somehow assign an artificial
cost to each operation in the sequence. This artificial
cost is called the _amortized cost_ of an operation. The
key property required of amortized cost is that the total
real cost of the sequence should be bounded by the total of
the amortized costs of all the operations. Then, for
purposes of analyzing an algorithm that, say, accesses a
data structure, it is okay to just use the amortized cost
instead of the actual cost of the operation. This will give
you correct results.
Note: There is sometimes flexibility in the assignment of
amortized costs.
There are going to be three approaches that we call:
The aggregate method
The banker's method (tokens in the data structure)
The physicist's method (potential functions)
(The physicist's method is just a slightly more formal
version of the banker's method, as we'll see.)
We'll illustrate these methods through some examples.
Example1: a binary counter
---------------------------------
Say we want to store a big binary counter in an array A:
Start all entries at 0. The operation we are going to
implement and analyze is that of counting.
The algorithm we'll use for incrementing this counter is the
usual one. We toggle bit A[0]. If it changed from 0 to 1,
then we toggle bit A[1], etc. We stop when a bit changes
from 0 to 1. The cost of an increment is the number of bits
that change.
A[m] A[m-1] ...... A[3] A[2] A[1] A[0] cost
---------------------------------------- ----
0 0 0 0 0 0
1
0 0 0 0 0 1
2
0 0 0 0 1 0
1
0 0 0 0 1 1
3
0 0 0 1 0 0
1
0 0 0 1 0 1
2
0 0 0 1 1 0
The number of bits that change when the increment produces a
number n is at most 1+floor(lg n). (That's just the number of
bits in the binary representation of n.)
Thus, in a sequence of n increments, worst-case cost per increment
is bounded by n(1+floor(lg n)) = O(n log n).
But, what is our *amortized* cost per increment? Answer: 2.
Proof 1 (aggregate method): how often do we flip A[0]?
Answer: every time. how often do we flip A[1]? Answer:
every other time. How often do we flip A[2]? Answer: every
4th time. Etc. So, total cost spent on flipping A[0] is n,
total cost of A[1] is floor(n/2), total cost on A[2] is
floor(n/4), etc. So, the total cost is:
total cost = n + floor(n/2) + floor(n/4) + ...
total cost <= n + n/2 + n/4 + n/8 + ... <= 2n
So the total cost is 2n, which means the amortized cost of
an increment is 2.
Proof 2 (banker's method): Let's us a kind of accounting
trick. On every bit that is a 1, let's keep a dollar on
that bit. So for example, if the current count is 6, we'd
have:
$ $
array: 0 .... 0 1 1 0
We'll use the convention that whenever we toggle a bit, we
must pay a dollar to do that.
Let's say we allocate $2 to do an increment. Let's see how
much it costs to do the increment. In general, a bunch of
low order bits change from 1 to 0, and then one bit changes
from a 0 to a 1, and the process terminates. For each of
the bits that changes from 1 to 0, we have a dollar sitting
on the bit to pay for toggling that bit. For the bit that
changes from a 0 to a 1, we have to pay a dollar to toggle
the bit, then put a dollar on that bit (for future use).
Thus, having allocated $2 for the increment always
guarantees that we will have enough money to pay for the
work, no matter how costly the increment actually is.
This completes proof 2 that the amortized cost of the
increment is 2.
Example 2: Implementing a FIFO queue with two stacks
----------------------------------------------------
Say you have a stack data type, and you need to implement a
FIFO queue. The stack has the usual POP and PUSH
operations, and the cost of each operation is 1.
We can implement a FIFO queue using two stacks as follows.
The FIFO has two operations: ENQUEUE and DEQUEUE:
ENQUEUE(x): Push x onto stack1.
DEQUEUE(): if stack2 is empty, then we POP the
entire contents of stack1 and PUSH it
into stack2. Now simply POP from
stack2 and return the result.
It's easy to see that this algorithm is correct. Here we'll
just worry about the running time. (I'm going to ignore the
cost of checking of stack2 is empty, and only measure the
cost in terms of the number of PUSHs and POPs that are
done.)
Claim: the amortized cost of ENQUEUE is 3 and DEQUEUE is 1.
Proof 1 (aggregate method): As an element flows through the
two-stack data structure, it's PUSHed at most twice and
POPPed at most twice. This shows that we can assign an
amortized cost of 4 to ENQUEUE and 0 to DEQUEUE.
To get the desired result, note that if an element is not
DEQUEUED it's only PUSHED twice and POPPED once. So the
cost of 3 is paid for by the cost of 3 per ENQUEUE. The
last POP is paid for by the DEQUEUE (if it happens).
Proof 2 (banker's method): Maintain a collection of tokens
on stack1. In fact, keep 2 tokens for each thing in the
stack.
When we ENQUEUE, we have three tokens to work with. We use
one to push the element onto stack1, and the other two are
put on the element for future use. When we have to move
stack1 into stack2, we have enough tokens in the stack to
pay for the move (one POP and one PUSH for each element).
Finally, the last pop done by the DEQUEUE is paid for by the
1 we allocated for it. QED.
Example 3: doubling array
-------------------------
We'll use an array to implement a stack that allows push and
pop operations. We represent the stack as an array, A[] and
an integer variable top that points to the top of the stack.
Here is a naive implementation of push and pop:
push(x): top++; A[top] = x;
pop; top--; return A[top+1]
These operations are both constant time (cost=1). The
problem is, what happens when the array gets full? To deal
with this, we keep another variable L, storing the size of
the array, and a variable k keeping count of the number of
elements of the array that are in use. When we are about to
overflow the available space (k=L), we allocate an array
twice as large, move the data over to the new array, free
the old array, and double L. This operation is called
"doubling". It will be convenient to analyze it as thought
it was a separate operation on the data strucure, that
occurs only when k=L.
If the stack is full, and has size L, and we apply the
doubling operation, the cost of the operation is L, because
we have to move L items into the new array. (The cost of
allocating and freeing the arrays is O(L).)
Starting from an empty stack, doing any sequence n pushes
and pops, how much does this cost?
First analysis: Total cost for pushes and pops is n.
Total cost for doubling is at worst 1 + 2 + 4 + ... n/2 + n
< 2n So, the total cost is 3n. Therefore we can say that
the amortized cost of an operation is 3.
Second analysis: Again, we use the financial approach.
We'll keep money lying around the data structure in the
following way.
$ $ $ $
$ $ $ $
+-------------------------------+
|x|x|x|x|x|x|x|x|x|x|x|x| | | | |
+-------------------------------+
^
|
midpoint
We'll keep $2 on each element stored in the stack that is
BEYOND THE MIDPOINT of the current array. In the normal
case when we do a push (the array is not full), we need $1
to do the work, and then at most $2 to put onto the the new
item we just pushed. Thus the cost is $3. (pop is even
cheaper.) Now what happens if we have to do a doubling
operation?
Before doubling:
$ $ $ $ $ $ $ $
$ $ $ $ $ $ $ $
+-------------------------------+
|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|
+-------------------------------+
^
|
midpoint
<--------------L--------------->
After doubling:
+-------------------------------+-------------------------------+
|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x| | | | | | | | | | | | | | | | |
+-------------------------------+-------------------------------+
^
|
midpoint
You can see that the money that we had on the items (L) was
sufficient to pay for all the work of doubling the array
(L). We conclude that if we allocate $3 for each operation,
we'll never run out of money. Thus the amortized cost of an
operation is 3.
In these examples, the financial model was not really
necessary to get the desired results. However, later we'll
see examples where this approach is necessary.
Potential Functions. (The Physicist's method)
---------------------------------------------
Let's say that instead of distributing our money all over
the data structure (as we did above), we keep it all in a
piggy bank. What's really important is how much money is in
the piggy bank. We'll call the amount of money in this bank
the "potential function" (Phi) for the problem.
So for the two problems above, we used the following two
potential functions:
Phi(counter) = # of one bits in the counter
Phi(queue) = 2 * the size of stack 1.
[ 2(k-L/2) if k >= L/2
Phi(stack) = [
[ 0 otherwise
(Here L is the current array size, and k is the number of
elements currently in the stack.)
Using this formalism we can define the amortized cost of an
operation. Say the system changes from state S to state S'
as a result of doing some operation. We define the
amortized cost of the operation as follows:
amortized cost = actual cost + Delta(Phi) =
= actual cost + Phi(S') - Phi(S)
This is simply the amount of additional money that we need
to maintain our piggy bank and to pay for the work.
For the counter, with the potential function given above:
amortized cost of increment <= 2
For the stack, with the potential function given above:
amortized cost of pop <= 3
How is this amortized cost related to actual cost? Let's
sum the above definition of amortized cost over all the
operations:
Sigma(amortized cost) = Sigma(actual cost) + Phi(final) - Phi(initial)
or
Sigma(actual cost) = Sigma(amortized cost) + Phi(initial) - Phi(final)
If the potential is always non-negative, and starts at zero
(as it is in our examples), then
Sigma(actual cost) <= Sigma(amortized cost)
In this more general framework, the potential can be
negative, and may not start at 0. So in general we have to
worry about the initial and final potentials.
Summary of using potential functions to do amortized
analysis:
(1) Pick a potential function that's going to work
(this is art)
(2) Using your potential function, bound the amortized
cost of the operations you're interested in.
(3) Bound Phi(initial) - Phi(final)
In terms of (1), one obvious point is that if the actual
cost of an operation is HIGH, and you want the amortized
cost to be LOW, then in this case the potential must
DECREASE by a lot to pay for it. This is illustrated in
both of the examples in this lecture.
We'll see in the next lecture just how essential this
formalism is for analyzing splay trees.
