Algorithms and Data
15: Amortized Analysis Professor Kevin Gold
In amortized analysis, we argue that the running time of the worst case
•
isn’t as bad as it seems, because operations are only infrequently expensive — even in the worst case.
•
Lots of cheap calls make up for an expensive call
As opposed to finding average case running time, amortized analysis
•
is still about the worst case, but counts more carefully
•
If some calls to a method are more expensive than others, it may make sense to try to compute the total work done across N calls, T(N)
Aggregate Analysis and
Amortized Cost
In such “aggregate analysis,” the amortized cost of the
•
method is the average across all calls, T(N)/N.
•
But it’s still an upper bound on the work done — as opposed to expected running time, which is the “average” running time people usually talk about
Thinking about amortized cost can avoid big-O bounds
•
that are too loose.
•
Multipop, Lazy Analysis
Suppose we have a stack with the usual push and pop
•
operations.
Push and pop are both O(1) – just change head of list
Now suppose we add “multipop” which is an operation that can pop k items, just by calling pop() k times. This is O(N) in the worst case (everything is in the stack and we pop it all)
•
So is the worst case time to do N push, pop, and
•
multipop operations O(N) * O(N) = O(N2)?
Multipop,
Aggregate Analysis
Aggregate analysis sums the total operations done over multiple calls The number of pop operations (including in multipop) is bounded by the
•
(often, N calls) to find the average work done per operation in the worst case
•
number of push operations.
• • •
• •
So we have at most O(N) pop operations of any kind Combined with O(N) pushes, that’s still O(N) work
So the amortized cost of all of these operations is O(N)/N = O(1). Multipop’s amortized cost is constant.
We expect N calls to take O(N) work, not O(N2).
This is a worst-case bound — no probability involved.
•
Suppose we’re incrementing a binary number from 0 up to a
k-bit number N. How many times do we flip bits?
In a worst case, we flip all k bits in one step (0111..1 becomes 1000…0)
•
Incrementing a Binary
Counter
So a first pass analysis says the
•
running time is O(kN) = O(N log N)
•
Amortized Analysis of
Flipping Bits in the Counter
To the right, the bits highlighted are those that change on the next step
Notice a pattern?
k-1 i ∞ i
Σi=0 (n/2) < n Σi=0 (1/2) = 2n = O(n)
N increments take O(N) flips, so the amortized number of flips per increment is O(1).
• • •
The “Accounting Method”
An interesting analysis trick is to actually assign different numbers from the actual costs of operations — “charging” more or less operations than they actually cost.
•
The algorithm’s “credit” is the amount it has been charged
•
for operations, minus its actual number of operations.
•
As long as the algorithm’s credit never goes negative, we can use what we “charged” as a bound on the actual number of operations.
For example, we can “prepay” for operations that will
•
happen later, making analysis easier.
The Accounting Method
with Multipop
Suppose we assign amortized costs of 2 to push, 0 to
•
pop, 0 to multipop.
With push, we essentially “prepay” for the pop or multipop
•
operation that would remove the element we push.
Every sequence of actions we can legally take keeps our
•
credit positive.
•
Thinking about the worst case of N push/pop/multipop calls, we get 2N = O(N) operations, or an amortized cost of O(1) operations per call.
•
An Accounting Method
Analysis of Bit-Flipping
Let the amortized cost of setting a bit to 1 be 2, and the
•
cost of flipping it back to 0 be 0.
“Prepay” for flipping the bit back
Our credit remains positive - bit can’t flip to 0 before it’s 1
Every time there is an increment, we set at most 1 bit to 1 - either the rightmost bit (no carry), or we carry until a bit to the left is set to 1.
• •
So N increments have an amortized number of flips of 2N =
•
O(N), matching our analysis from before.
• • •
Deriving the Potential Method
How do we find good amortized costs to charge for ops?
In analyzing multipop, notice how our costs for the accounting method were
Push: 1 + 1 = 2 Pop: 1 - 1 = 0 Multipop: k - k = 0
•
The potential method is one way
•
(true cost) + ((stack elements after op) - (stack elements before op))
Define the potential Φ(s) of a stack to be the number of elements in it. That
•
represents how many operations we’ve prepaid for.
Then our amortized costs can all have the form c + Φ(s’) - Φ(s), where Φ(s’) is
•
the new potential after the operation and Φ(s) is the old potential.
•
•
•
•
The Potential Method in
General
In the potential method, there is some function Φ(s) that takes a data structure involved in the algorithm and returns a non-negative number.
Also, Φ(s0) = 0 ... no potential saved up to start.
Setting the amortized costs of operations to
c + Φ(s’) - Φ(s), where c is the true cost, s’ is the data structure after the operation, and s is the data structure before the operation, creates a set of costs that is guaranteed to sum to an upper bound of the true cost.
Σi (ci + Φ(si) - Φ(si-1)) = (Σi ci) + Φ(sN) - Φ(s0) ≥ Σi ci
“telescoping sum” to true cost and non- negative potential diifference
Sum of amortized costs
Potential Method for
Counting Bit Flips
Let the potential Φ(s) be the number of 1’s in the binary
•
counter. This starts 0 and is non-negative.
Suppose increment i resets ti bits to 0. We argued before that The difference in potentials Φ(si) - Φ(si-1) between the previous
•
there can be at most 1 bit set to 1.
•
step and the current step is therefore 1 - ti. (gained 1, lost ti)
•
And the actual work done is ti + 1.
So set the amortized cost of increments to (ti + 1) + (1 - ti)= 2,
•
making the bits flipped for N increments O(N).
ArrayList.add() Sometimes Requires ArrayList.size() operations
ArrayList allows constant time access to its elements because it’s really an
•
array “under the hood”
But arrays have a fixed size, while ArrayList allows us to Add() arbitrarily many elements?
•
many elements. So what happens to this array when we try to add too
•
Memory immediately adjacent to the array is probably being used for other program stuff, and we don’t want to fragment the array (speed issues). We’ve got to ask for a contiguous block of memory and copy all the elements into this bigger array
Common choice: copy to an array twice as big. (Java spec is vague)
•
Copying a whole array is O(N) operations, so it looks at first as if adding N
•
elements may be O(N2) in the worst case
• • •
lg N
Work for N adds: N + Σ 2j = N + “11111...1” < N + 2N = 3N
j=0
So amortized cost of an add() is constant: 3.
ArrayList.Add():
Aggregate Analysis
Let’s assume we recopy to an array twice the size of the For N elements, the array will double lg N times
•
current one when we’ve run out of room
•
The cost of the jth doubling is 2j if we start from size 0 Also, N basic array assignments for N elements
•
(unlikely start, but this is an upper bound)
1+lg N
• •
• • •
The Three Amortized
Operations of Add() Can think about this amortized cost this way — assume we have just
•
expanded to a size m array and have no “credit” stored up.
m/2 elements currently in the array
Budgeting 3 operations for each of the next m/2 adds “pays” for:
The actual insertion of this element in the array
Moving this element once, when the array is expanded again
Moving one of the m/2 elements that already used up their “saved credit” on the last move.
When the array is doubled, the budgeted costs will match the exact costs
•
again — no credit left.
•
The preceding analysis shows how the fullness of the array (“load factor”) can act as a potential function, representing saved up amortized costs
•
•
•
Potential Function
Analysis of Add()
Let Φ(N) = 2N - array.length
0 for N = 0 or array.length == 2N
2N - N = N when array full
Amortized cost without an array doubling is then
•
c + (Φ(s’) - Φ(s)) = (1 + increase potential by 2) = 3
Amortized cost with array doubling because of extra element is
•
c + (Φ(s’) - Φ(s)) = (1 + N) + (lose N potential, then gain 2) = 3
What are These Potential
Functions For, Again?
We could try the “accounting method” and “prepay” for some operations, but it may not be obvious how to appropriately “cost” operations such that we’re never cheating and paying less than the actual number of operations.
Rather than trying to think about sequences of operations remaining net positive, it can be easier to define a function on the data structure that is clearly 0 at first and always non-negative.
Then setting the amortized cost of an operation to its true cost plus the change to the potential guarantees that “cheating” never happens in the accounting.
We’re about to see a case where a different method would be tough.
We had a nice closed-form formula for the amortized cost of add() with our
•
aggregate analysis, but such exact analysis is hard sometimes.
•
•
•
•
•
Removing Elements From a Growable Array
Consider still an ArrayList-like structure
If we remove enough elements, maybe we should
•
move to a smaller array to free up memory
Should we move to a smaller array if we drop below
•
array.length/2 elements?
•
If we double the array adding element length/2+1 and halve the array on deleting it, we could end up “thrashing” as we add, delete, add, delete, performing Ө(N) copy operations each time.
Shrinking at Length/2
Elements is Terrible
No amount of amortization saves us from this worst case.
•
N operations would be Ө(N2).
•
Amortization only results in lower running times when there is some guarantee the expensive operations are somewhat infrequent, their costs proportional to the work already done.
Using Amortization to Think
About the Deletion Problem
We need to have done enough operations to “pay for” the
•
contraction of the array.
(meaning, change our strategy to make deletion less
•
relatively frequent)
Just after doubling, we had zero potential. There haven’t been
•
enough operations to “fund” a deletion.
Let’s change our potential function so that deletions also
•
contribute to the “fund” for future expensive ops
And change our policy to require a buildup in the “fund” before
•
downsizing
A Potential Function for Dynamic Array Expansion & Contraction
Change in policy: shrink array when the number of
•
elements hits array.length/4
• •
• • •
Φ(N) = 2N - array.length if N >= array.length/2 Φ(N) = array.length/2 – N if N < array.length/2
Φ(N) = 0 when N = array.length/2
Φ(N) = N when N = array.length
Φ(N) = array.length/4 when N = array.length/4
Calculating Amortized Costs of Normal Adds and Deletes
Φ(N) = 2N - array.length if N >= array.length/2 Φ(N) = array.length/2 – N if N < array.length/2
Add with N >= array.length/2:
1 + (2 potential change) = 3
• • •
Add with N < array.length/2:
Delete with N >= array.length/2:
•
1 + (-1 potential change) = 0
•
1 + (-2 potential change) = -1 (we overcharged on the add!)
Delete with N < array.length/2:
•
1 + (+1 potential change) = 2
Calculating Amortized Costs of the Big Adds and Deletes
Φ(N) = 2N - array.length if N >= array.length/2 Φ(N) = array.length/2 – N if N < array.length/2
Add with N = array.length, need to resize up:
1 + N + (-N+2 potential change) = 3
• • •
Remove to get N = array.length/4, resize down:
•
1 + array.length/4 + (-array.length/4 potential) = 1
•
All operations’ amortized costs are bounded by a constant — so add() and delete() are amortized cost O(1) in these growable, shrinkable arrays.
Analyzing Splay Trees
A splay tree is a binary search tree that shifts
This can make accesses for real data very fast, since
•
elements up to the root whenever they’re accessed.
•
recently used data tends to be used again soon
Splay trees are in the worst case linear time to
•
access, since they could be totally unbalanced
But amortized analysis will show the worst case is
•
better thought of as O(log n)
•
and Rotations
In a binary search tree node, left.key <= this.key <= right.key
Binary Search Trees
We can preserve this property while changing which node is the parent of
•
which in a local area
This is called a “rotation” of the tree. If B is A’s parent, make A B’s parent,
•
handing off A’s child to B if necessary.
4
25
rotate about 2&4
2
4
1
13 35
•
the root:
•
•
•
Zig, Zig-Zig, Zig-Zag
Zig: do this if parent is root. See prev slide, where we “zig” on 2. Zig-Zig: do this if a left-child of a left child, or right child of a right child.
Rotate to move parent above grandparent, then rotate above parent. Zig-Zag: otherwise, rotate to move above parent, then rotate to move
A splay tree uses the following operations to get an accessed node up to
above former grandparent.
4
1
2
251
4
2
4
5
13
Zig-Zig
3
5
3
•
the root:
•
•
•
Zig, Zig-Zig, Zig-Zag
Zig: do this if parent is root. See prev slide, where we “zig” on 2. Zig-Zig: do this if a left-child of a left child, or right child of a right child.
Rotate to move parent above grandparent, then rotate above parent. Zig-Zag: otherwise, rotate to move above parent, then rotate to move
A splay tree uses the following operations to get an accessed node up to
above former grandparent.
4
25
4
35
2
3
24
13
Zig-Zag
1
15
Some Splay Tree Operations
Splay node: zig, zig-zig, or zig-zag until a node is
•
at the root.
Access node: Binary search down tree, then splay
•
accessed node.
Insert node: Recur down tree to insert node, then
•
splay node.
Amortized Cost of Splaying
•
•
•
Let Φ(T) = Σt rank(t).
Assume x is target node, p parent, g grandparent
Zig amortized cost =
1 + (rank’(x) - rank(x)) + (rank’(p) - rank(p)) =
1 + rank’(p) - rank(x) ≤ 1 + rank’(x) - rank(x)
Define size(t) to be the number of nodes in the subtree
•
rooted at node t.
Define rank(t) to be lg(size(t)). We’ll use rank’(t) to signify
•
rank after an operation.
rank’(x) = rank(p) rank’(p) < rank’(x)
Amortized Cost of Splaying
Define rank(t) to be lg(size(t)). We’ll use rank’(t) to signify rank after an operation. Let Φ(T) = Σt rank(t).
Zig-zig amortized cost =
2 + (rank’(x) - rank(x)) + (rank’(p) - rank(p)) + (rank’(g) - rank(g))
•
•
•
•
•
Similar calculation for zig-zag operation — the change in potential is at most
2 (rank’(x)-rank(x))
The sum of costs over the splay is ≤ Σ(2 + 2(rank’(x)-rank(x)))
≤ Σ3(rank’(x)-rank(x))) over the path of x. The terms telescope and the final amortized cost is ≤ 3(rank(root)-rank(x)) which is at most 3(lg(N) - 0) = O(lg N).
Cancel rank(g) and rank’(x): rank(x) < rank(p):
rank’(x) > rank’(p):
rank’(g) < rank’(x):
= 2 + rank’(p)+rank’(g)-rank(x)-rank(p)
≤ 2 + rank’(p)+rank’(g) - 2 rank(x)
≤ 2 + rank’(x)+rank’(g) - 2 rank(x)
≤ 2 + 2 (rank’(x)-rank(x))
Summary: Amortized Costs
Amortized costs are a way of getting closer to the true Three methods:
•
number of operations that a series of operations will take.
•
Aggregate analysis: Sum all operations over N
•
operations, find the average cost
Accounting method: Come up with a cost structure such
•
that some operations “overpay” to account for future ops
Potential method: Create a potential function on the data
•
structure that tracks what our remaining “balance” is