1. Review Sites
  2. Home
  3. Modules
  4. Amortized analysis
  5. Notes on amortized analysis

Outline

  1. Amortized Analysis: The General Idea
  2. Multipop Example
  3. Aggregate Analysis
  4. Accounting Method
  5. Potential Method
  6. Dynamic Table Example (first look)
  7. Other Examples

Amortized Analysis: The General Idea

We have already used aggregate analysis several times in this course. For example, when analyzing the BFS and DFS procedures, instead of trying to figure out how many times their inner loops

for each _v_ ∈ G.Adj[_u_]

execute (which depends on the degree of the vertex being processed), we realized that no matter how the edges are distributed, there are at most |E| edges, so in aggregate across all calls the loops will execute |E| times.

But that analysis concerned itself only with the complexity of a single operation. In practice a given data structure will have associated with it several operations, and they may be applied many times with varying frequency.

Sometimes a given operation is designed to pay a larger cost than would otherwise be necessary to enable other operations to be lower cost.

Example: Red-black tree insertion. We pay a greater cost for balancing so that future searches will remain O(lg n).

Another example: Java Hashtable.

It is “fairer” to average the cost of the more expensive operations across the entire mix of operations, as all operations benefit from this cost.

Here, “average” means average cost in the worst case (thankfully, no probability is involved, which greatly simplifies the analysis).

We will look at three methods. The notes below use Stacks with Multipop to illustrate the methods. See the text for binary counter examples.

(We have already seen examples of aggregate analysis throughout the semseter. We will see examples of amortized analysis later in the semester.)

Multipop Example

We already have the stack operations:

Suppose we add a Multipop (this is a generalization of ClearStack, which empties the stack):

The example shows a Multipop(S,4) followed by another where k ≥ 2.

Running time of Multipop:

What is the worst case of a sequence of n Push, Pop and Multipop operations?

Using our existing methods of analysis we can identify a loose bound::

Aggregate Analysis

We can tighten this loose bound by aggregating the analysis over all n operations:

This analysis shows O(1) per operation on average in a sequence of n operations without using any probabilities of operations.

See text for example of aggregate analysis of binary counting. An example of aggregate analysis of dynamic tables is at the end of these notes.

Some of our previous analyses with indicator random variables have been a form of aggregate analysis, e.g., our analysis of the expected number of inversions in sorting, Topic 5 Notes.

Aggregate analysis treats all operations equally. The next two methods let us give different operations different costs, so are more flexible.

Accounting Method

Metaphor:

Amortized cost = amount we charge each operation.

This differs from aggregate analysis:

When an operation is overcharged (amortized cost > actual cost), the difference is associated with specific objects in the data structure as credit.

We use this credit to pay for operations whose actual cost > amortized cost.

The credit must never be negative. Otherwise the amortized cost may not be an upper bound on actual cost for some sequences.

Let

Require ∑i=1,n__ĉi ≥ ∑i=1,n__ci for all sequences of n operations. That is, the difference between these sums always ≥ 0: we never owe anyone anything.

Stack Example

Whenever we Push an object (at actual cost of 1 cyberdollar), we potentially have to pay CY$1 in the future to Pop it, whether directly or in Multipop.

To make sure we have enough money to pay for the Pops, we charge Push CY$2.

Since each object has CY$1 credit, the credit can never go negative.

The total amortized cost ĉ = ∑i=1,n__ĉi for any sequence of n operations is an upper bound on the total actual cost c = ∑i=1,n__ci for that sequence.

Since ĉ = O(n), also c = O(n).

Note: we don’t actually store cyberdollars in any data structures. This is just a metaphor to enable us to compute an amortized upper bound on costs.

Potential Method

Instead of credit associated with objects in the data structure, this method uses the metaphor of potential associated with the entire data structure.

(I like to think of this as potential energy, but the text continues to use the monetary metaphor.)

This is the most flexible of the amortized analysis methods, as it does not require maintaining an object-to-credit correspondence.

Let

Potential Function Φ: D_i_ -> ℜ, and we say that Φ(D_i_) is the potential associated with data structure D_i_.

We define the amortized cost ĉi to be the actual cost ci plus the change in potential due to the _i_th operation:

ĉi = ci + Φ(D_i_) − Φ(D_i-1_)

The total amortized cost across n operations is:

∑i=1,n__ĉi = ∑i=1,n(ci + Φ(D_i_) - Φ(D_i-1_)) = (∑i=1,n__ci) + (Φ(D_n_) - Φ(D0))

(The last step is taken because the middle expression involves a telescoping sum: every term other than D_n_ and D0 is added once and subtracted once.)

If we require that Φ(D_i_) ≥ Φ(D0) for all i then the amortized cost will always be an upper bound on the actual cost no matter which _i_th step we are on.

This is usually accomplished by defining Φ(D0) = 0 and then showing that Φ(D_i_) ≥ 0 for all i. (Note that this is a constraint on Φ, not on ĉ. ĉ can go negative as long as Φ(D_i_) never does.)

Stack Example

Define Φ(D_i_) = number of objects in the stack.

Then Φ(D0) = 0 and Φ(D_i_) ≥ 0 for all i, since there are never less than 0 objects on the stack.

Charge as follows (recalling that ĉi = ci + Φ(D_i_) - Φ(D_i-1_)):

Since we charge 2 for each Push and there are O(n) Pushes in the worst case, the amortized cost of a sequence of n operations is O(n).

Does it seem strange that we charge Pop and Multipop 0 when we know they cost something?

Application: Dynamic Tables

There is often a tradeoff between time and space, for example, with hash tables. Bigger tables give faster access but take more space.

Dynamic tables, like the Java Hashtable, grow dynamically as needed to keep the load factor reasonable.

Reallocation of a table and copying of all elements from the old to the new table is expensive!

But this cost is amortized over all the table access costs in a manner analogous to the stack example: We arrange matters such that table-filling operations build up sufficient credit before we pay the large cost of copying the table; so the latter cost is averaged over many operations.

A Familiar Definition

Load factor α = num/size, where num = # items stored and size = the allocated size of the table.

For the boundary condition of size = num = 0, we will define α = 1.

We never allow α > 1 (no chaining).

Insertion Algorithm

We’ll assume the following about our tables. (See Exercises 17.4-1 and 17.4-3 concerning different assumptions.):

When the table becomes full, we double its size and reinsert all existing items. This guarantees that α ≥ 1/2, so we are not wasting a lot of space.

Table-Insert (T,x)
1   if T.size == 0
2       allocate T.table with 1 slot 
3       T.size = 1
4   if T.num == T.size
5       allocate newTable with 2*T.size slots
6       insert all items in T.table into newTable
7       free T.table
8       T.table = newTable 
9       T.size = 2*T.size 
10  insert x into T.table 
11  T.num = T.num + 1

Each elementary insertion has unit actual cost. Initially T.num = T.size= 0.

Aggregate Analysis of Dynamic Table Expansion

Charge 1 per elementary insertion. Count only elementary insertions, since all other costs are constant per call.

ci = actual cost of _i_th operation.

A sloppy analysis: In a sequence of n operations where any operation can be O(n), the sequence of n operations is O(_n_2).

This is “correct”, but inprecise: we rarely expand the table! A more precise account of ci:

Then we can sum the total cost of all ci for a sequence of n operations:

Explain: Why the n? What is the summation counting? Why does the summation start at j = 0? Why does it end at j = lg n?

Therefore, the amortized cost per operation = 3: we are only paying a small constant price for the expanding table.

The text also gives accounting and potential analyses of table expansion.

This analysis assumed that the table never shrinks. See section 17.4 (and your homework) for an analysis using the potential method that covers shrinking tables.

Other Examples

Here are some other algorithms for which amortized analysis is useful:

Red-Black Trees

An amortized analysis of Red-Black Tree restructuring (Problem 17-4 of CLRS) improves upon our analysis earlier in the semester:

Self-Organizing Lists

Splay Trees

To Be Continued

Amortized analysis will be used in analyses of

Dan Suthers Last modified: Sun Mar 16 02:03:09 HST 2014
Images are from the instructor’s material for Cormen et al. Introduction to Algorithms, Third Edition.