In an * amortized analysis*, the time required to perform a sequence of data-structure operations is averaged over all the operations performed. Amortized analysis can be used to show that the average cost of an operation is small, if one averages over a sequence of operations, even though a single operation might be expensive. Amortized analysis differs from average-case analysis in that probability is not involved; an amortized analysis guarantees the

In the * aggregate method* of amortized analysis, we show that for all

In our first example of the aggregate method, we analyze stacks that have been augmented with a new operation. Section 11.1 presented the two fundamental stack operations, each of which takes *O*(1) time:

PUSH(*S*, *x*) pushes object *x* onto stack *S*.

POP(*S*) pops the top of stack *S* and returns the popped object.

The situation becomes more interesting if we add the stack operation MULTIPOP(*S, k*), which removes the *k* top objects of stack *S*, or pops the entire stack if it contains less than *k* objects. In the following pseudocode, the operation STACK-EMPTY returns TRUE if there are no objects currently on the stack, and FALSE otherwise.

MULTIPOP(S,k)

1whilenot STACK-EMPTY(S) andk0

2doPOP(S)

3kk- 1

Figure 18.1 shows an example of MULTIPOP.

As another example of the aggregate method, consider the problem of implementing a *k-*bit binary counter that counts upward from 0. We use an array *A*[0 . . *k* - 1] of bits, where *length*[*A*] = *k*, as the counter. A binary number *x* that is stored in the counter has its lowest-order bit in *A*[0] and its highest-order bit in *A*[*k* - 1], so that . Initially, *x* = 0, and thus *A*[*i*] = 0 for *i* = 0, 1, . . . , *k* - 1. To add 1 (modulo 2* ^{k}*) to the value in the counter, we use the following procedure.

INCREMENT(A)

1i0

2whilei<length[A] andA[i] = 1

3doA[i] 0

4ii+ 1

5ifi<length[A]

6thenA[i] 1

If a MULTIPUSH operation were included in the set of stack operations, would the *O*(1) bound on the amortized cost of stack operations continue to hold?

Show that if a DECREMENT operation were included in the *k-*bit counter example, *n* operations could cost as much as (*nk*) time.

In the * accounting method* of amortized analysis, we assign differing charges to different operations, with some operations charged more or less than they actually cost. The amount we charge an operation is called its

To illustrate the accounting method of amortized analysis, let us return to the stack example. Recall that the actual costs of the operations were

PUSH 1 ,

POP 1 ,

MULTIPOP min(k,s) ,

PUSH 2 ,

POP 0 ,

MULTIPOP 0 .

As another illustration of the accounting method, we analyze the INCREMENT operation on a binary counter that starts at zero. As we observed earlier, the running time of this operation is proportional to the number of bits flipped, which we shall use as our cost for this example. Let us once again use a dollar bill to represent each unit of cost (the flipping of a bit in this example).

Redo Exercise 18.1-3 using an accounting method of analysis.

Suppose we wish not only to increment a counter but also to reset it to zero (i.e., make all bits in it 0). Show how to implement a counter as a bit vector so that any sequence of *n* INCREMENT and RESET operations takes time *O*(*n*) on an initially zero counter. (*Hint*: Keep a pointer to the high-order 1.)

Instead of representing prepaid work as credit stored with specific objects in the data structure, the * potential method* of amortized analysis represents the prepaid work as "potential energy,"or just "potential," that can be released to pay for future operations. The potential is associated with the data structure as a whole rather than with specific objects within the data structure.

The potential method works as follows. We start with an initial data structure *D*_{0 }on which *n *operations are performed. For each *i* = 1, 2, . . . , *n*, we let *c _{i}* be the actual cost of the

The second equality follows from equation (3.7), since the (*D _{i}*) telescope.

To illustrate the potential method, we return once again to the example of the stack operations PUSH, POP, and MULTIPOP. We define the potential function on a stack to be the number of objects in the stack. For the empty stack *D*_{0} with which we start, we have (*D*_{0}) = 0. Since the number of objects in the stack is never negative, the stack *D _{i }*that results after the

(D) 0_{i}

= (D_{0}).

(D) - (_{i}D1) = (_{i - }s+ 1 ) -s

= 1 .

By equation (18.1), the amortized cost of this PUSH operation is

(D) - (_{i}D1) = -_{i-}k'.

Thus, the amortized cost of the MULTIPOP operation is

Similarly, the amortized cost of an ordinary POP operation is 0.

As another example of the otential method, we again look at incrementing a binary counter. This time, we define the potential of the counter after the *i*th INCREMENT operation to be *b _{i}*, the number of 1's in the counter after the

(D) - (_{i}D-1)_{i}(b-1 -_{i}t+ 1) -_{i}b-1_{i}

= 1 -t_{i}.

The amortized cost is therefore

Redo Exercise 18.1-3 using a potential method of analysis.

Consider an ordinary binary heap data structure with *n *elements that supports the instructions INSERT and EXTRACT-MIN in *O*(lg *n*) worst-case time. Give a potential function such that the amortized cost of INSERT is *O*(lg *n*) and the amortized cost of EXTRACT-MIN is *O*(1), and show that it works.

In some applications, we do not know in advance how many objects will be stored in a table. We might allocate space for a table, only to find out later that it is not enough. The table must then be reallocated with a larger size, and all objects stored in the original table must be copied over into the new, larger table. Similarly, if many objects have been deleted from the table, it may be worthwhile to reallocate the table with a smaller size. In this section, we study this problem of dynamically expanding and contracting a table. Using amortized analysis, we shall show that the amortized cost of insertion and deletion is only *O*(1), even though the actual cost of an operation is large when it triggers an expansion or a contraction. Moreover, we shall see how to guarantee that the unused space in a dynamic table never exceeds a constant fraction of the total space.

We shall find it convenient to use a concept introduced in our analysis of hashing (Chapter 12). We define the **load factor**** **(*T*) of a nonempty table *T* to be the number of items stored in the table divided by the size (number of slots) of the table. We assign an empty table (one with no items) size 0, and we define its load factor to be 1. If the load factor of a dynamic table is bounded below by a constant, the unused space in the table is never more than a constant fraction of the total amount of space.

Let us assume that storage for a table is allocated as an array of slots. A table fills up when all slots have been used or, equivalently, when its load factor is 1.^{1} In some software environments, if an attempt is made to insert an item into a full table, there is no alternative but to abort with an error. We shall assume, however, that our software environment, like many modern ones, provides a memory-management system that can allocate and free blocks of storage on request. Thus, when an item is inserted into a full table, we can * expand* the table by allocating a new table with more slots than the old table had and then copy items from the old table into the new one.

TABLE-INSERT(T,x)

1ifsize[T] = 0

2thenallocatetable[T] with 1 slot

3size[T] 1

4ifnum[T] =size[T]

5thenallocatenew-tablewith 2size[T] slots

6 insert all items intable[T] intonew-table

7 freetable[T]

8table[T]new-table

9size[T] 2size[T]

10 insertxintotable[T]

11num[T]num[T] + 1

The total cost of *n* TABLE-INSERT operations is therefore

By using the accounting method, we can gain some feeling for why the amortized cost of a TABLE-INSERT operation should be 3. Intuitively, each item pays for 3 elementary insertions: inserting itself in the current table, moving itself when the table is expanded, and moving another item that has already been moved once when the table is expanded. For example, suppose that the size of the table is *m* immediately after an expansion. Then, the number of items in the table is *m*/2, and the table contains no credit. We charge 3 dollars for each insertion. The elementary insertion that occurs immediately costs 1 dollar. Another dollar is placed as credit on the item inserted. The third dollar is placed as credit on one of the *m*/2 items already in the table. Filling the table requires *m*/2 additional insertions, and thus, by the time the table contains *m* items and is full, each item has a dollar to pay for its reinsertion during the expansion.

The potential method can also be used to analyze a sequence of *n* TABLE- INSERT operations, and we shall use it in Section 18.4.2 to design a TABLE-DELETE operation that has *O*(1) amortized cost as well. We start by defining a potential function that is 0 immediately after an expansion but builds to the table size by the time the table is full, so that the next expansion can be paid for by the potential. The function

(T) = 2num[T] -size[T]

the load factor of the dynamic table is bounded below by a constant, and

the amortized cost of a table operation is bounded above by a constant.

We assume that cost can be measured in terms of elementary insertions and deletions.

I, D, D, I, I, D, D, I, I,... ,

The difficulty with this strategy is obvious: after an expansion, we do not perform enough deletions to pay for a contraction. Likewise, after a contraction, we do not perform enough insertions to pay for an expansion.

We omit the code for TABLE-DELETE, since it is analogous to TABLE-INSERT. It is convenient to assume for analysis, however, that if the number of items in the table drops to 0, the storage for the table is freed. That is, if *num*[*T*] = 0, then *size*[*T*] = 0.

We can now use the potential method to analyze the cost of a sequence of *n* TABLE-INSERT and TABLE-DELETE operations. We start by defining a potential function that is 0 immediately after an expansion or contraction and builds as the load factor increases to 1 or decreases to 1/4. Let us denote the load factor of a nonempty table *T* by (*T*) = *num*[*T*]*/size*[*T*]*.* Since for an empty table, *num*[*T*] = *size*[*T*] = 0 and [*T*] = 1, we always have *num*[*T*] = (*T*) * size*[*T*], whether the table is empty or not. We shall use as our potential function

If1 < 1/2 but_{i-}1/2, then_{i}

Thus, the amortized cost of a TABLE-INSERT operation is at most 3.

Suppose that we wish to implement a dynamic, open-address hash table. Why might we consider the table to be full when its load factor reaches some value that is strictly less than 1? Describe briefly how to make insertion into a dynamic, open-address hash table run in such a way that the expected value of the amortized cost per insertion is *O*(1). Why is the expected value of the actual cost per insertion not necessarily *O*(1) for all insertions?

(T) = |2num[T] -size[T]|,

18-1 Bit-reversed binary counter

Chapter 32 examines an important algorithm called the Fast Fourier Transform, or FFT. The first step of the FFT algorithm performs a * bit-reversal permutation *on an input array

We can express each index *a* as a *k*-bit sequence *a _{k-}*1,

rev(_{k}a1,_{k-}a,...,_{k-2}a_{0}) = (a_{0, }a_{1},...,a1 ;_{k-}

We can use an algorithm based on an amortized analysis to improve the running time of the bit-reversal permutation. We maintain a "bit-reversed counter " and a procedure BIT-REVERSED-INCREMENT that, when given a bit-reversed-counter value** ***a***, **produces rev* _{k}*(rev

0000, 1000, 0100, 1100, 0010, 1010,... = 0, 8, 4, 12, 2, 10,... .

18-2 Making binary search dynamic

Binary search of a sorted array takes logarithmic search time, but the time to insert a new element is linear in the size of the array. We can improve the time for insertion by keeping several sorted arrays.

**c****. **Discuss how to implement DELETE.

18-3 Amortized weight-balanced trees

Consider an ordinary binary search tree augmented by adding to each node *x* the field *size*[*x*] giving the number of keys stored in the subtree rooted at *x*. Let be a constant in the range 1/2 < 1. We say that a given node *x *is * -balanced* if

size[left[x]]^{.}size[x]

size[right[x]]^{.}size[x].

(x) = |size[left[x]] -size[right[x]]| ,

and we define the potential of *T* as

where *c* is a sufficiently large constant that depends on .