15-451 Algorithms
February 7th, 2006
D. Sleator
Amortized analysis --- growing and shrinking a table
I'm sure you all know the trick of doubling an array when it needs to
grow. Then the amortized cost of all the growing operations is still
O(1). Why? Because if the array ends up of size N, the total cost of
all the doublings is 1+2+4+...N, which is at most 2N. And you needed
the array to be size at least N/2 (or the last doubling would not have
been done). Thus the cost of all the doublings is at most 4 times the
number of insertions.
[
This can be proven using a potential, of course.
Let s = number of things in the array, let n be the current size of
the array. Here's the potential:
Phi(n,s) = 0 if s4) then shrink()
now delete the object from the table
(cost of delete part is 1)
Lemma: The amortized cost of an insertion or deletion are
bounded by 5.
Proof: Let the potential be the following:
Phi(n,s) = 4|s-n/2|
What is the amortized cost of an insertion? It's the actual cost plus
the change in potential. A grow() may or may not happen as a result
of an insertion. If a grow() occurs, what is the amortized cost of
it? Before the grow() the potential is 4|n-n/2| = 2n. After the grow
the potential is 0. The actual cost of the grow is 2n. Thus the
amortized cost of the grow is 0.
What about the rest of the insert?
actual cost of insert = 1
change in potential <= 4.
====> amortized cost of insert <= 5.
What about delete? If a shrink() happens, then the potential
decreases by n, and the cost is n, so the amortized cost of shrink()
is 0. What about the rest of the delete:
actual cost of delete = 1
change in potential <= 4.
====> amortized cost of delete <= 5.
This completes the proof. QED.
Theorem: The total cost of a sequence of N insertions and deletions is
at most 5N + 8.
Proof: The amortized and real costs are related as follows:
SUM (actual costs) <= SUM(amortized costs)
+ initial_potential - final_potential
The initial potential is 8. The final potential is non-negative.
The sum of the amortized costs are 5. QED.
Actually, it's easy to get rid of the "+8" part. All we have to do
is change the potential for n=4 to the following:
[ 4|s-2| if s >= 2
Phi(4,s) = [
[ 0 otherwise
Thus, we've zeroed the potential for the case when the initial array
of size 4 is less than half full. The proof still goes through,
because we never shrink an array of size 4, and this part of the
potential is not important. This new potential has an initial value
of 0, completing the proof.