17.3 The potential method

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₀ on which n operations are performed. For each i = 1, 2, ..., n, we let c_i be the actual cost of the ith operation and D_i be the data structure that results after applying the ith operation to data structure D_i-1. A potential function Φ maps each data structure D_i to a real number Φ(D_i), which is the potential associated with data structure D_i. The amortized cost of the ith operation with respect to potential function Φ is defined by

(17.2)

The amortized cost of each operation is therefore its actual cost plus the increase in potential due to the operation. By equation (17.2), the total amortized cost of the n operations is

(17.3)

The second equality follows from equation (A.9), since the Φ(D_i) terms telescope.

If we can define a potential function Φ so that Φ(D_n) ≥ Φ(D₀), then the total amortized cost is an upper bound on the total actual cost . In practice, we do not always know how many operations might be performed. Therefore, if we require that Φ (D_i) ≥ Φ (D₀) for all i, then we guarantee, as in the accounting method, that we pay in advance. It is often convenient to define Φ (D₀) to be 0 and then to show that Φ (D_i) ≥ 0 for all i. (See Exercise 17.3-1 for an easy way to handle cases in which Φ(D₀) ≠ 0.)

Intuitively, if the potential difference Φ(D_i) - Φ(D_i-1) of the ith operation is positive, then the amortized cost represents an overcharge to the ith operation, and the potential of the data structure increases. If the potential difference is negative, then the amortized cost represents an undercharge to the ith operation, and the actual cost of the operation is paid by the decrease in the potential.

The amortized costs defined by equations (17.2) and (17.3) depend on the choice of the potential function Φ. Different potential functions may yield different amortized costs yet still be upper bounds on the actual costs. There are often trade-offs that can be made in choosing a potential function; the best potential function to use depends on the desired time bounds.

Stack operations

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₀ with which we start, we have Φ(D₀) = 0. Since the number of objects in the stack is never negative, the stack D_i that results after the ith operation has nonnegative potential, and thus

Φ(D_i)	≥	0
	=	Φ(D₀).

The total amortized cost of n operations with respect to Φ therefore represents an upper bound on the actual cost.

Let us now compute the amortized costs of the various stack operations. If the ith operation on a stack containing s objects is a PUSH operation, then the potential difference is

Φ(D_i) - Φ(D_i-1)	=	(s + 1) -s
	=	1

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

	=	c_i + Φ(D_i) - Φ (D_i-1)
	=	1 + 1
	=	2

Suppose that the ith operation on the stack is MULTIPOP(S, k) and that ′ = min(k, s) objects are popped off the stack. The actual cost of the operation is ′, and the potential difference is

Φ(D_i) - Φ(D_i-1) - -′.

Thus, the amortized cost of the MULTIPOP operation is

	=	c_i + Φ(D_i) - Φ(D_i-1)
	=	′ - ′
	=	0.

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

The amortized cost of each of the three operations is O(1), and thus the total amortized cost of a sequence of n operations is O(n). Since we have already argued that Φ(D_i) ≥ Φ(D₀), the total amortized cost of n operations is an upper bound on the total actual cost. The worst-case cost of n operations is therefore O(n).

Incrementing a binary counter

As another example of the potential method, we again look at incrementing a binary counter. This time, we define the potential of the counter after the ith INCREMENT operation to be b_i , the number of ′s in the counter after the ith operation.

Let us compute the amortized cost of an INCREMENT operation. Suppose that the ith INCREMENT operation resets t_i bits. The actual cost of the operation is therefore at most t_i + 1, since in addition to resetting t_i bits, it sets at most one bit to 1. If b_i = 0, then the ith operation resets all k bits, and so b_i-1 = t_i = k. If b_i > 0, then b_i = b_i-1 - t_i + 1. In either case, b_i ≤ b_i-1 - t_i + 1, and the potential difference is

Φ(D_i) - Φ(D_i-1)	≤	(b_i-1 - t_i + 1) - b_i-1
	=	1 - t_i.

The amortized cost is therefore

	=	c_i + Φ(D_i) - Φ(D_i-1)
	≤	(t_i + 1) + (1 - t_i)
	=	2.

If the counter starts at zero, then Φ(D₀) = 0. Since Φ(D_i) ≥ 0 for all i, the total amortized cost of a sequence of n INCREMENT operations is an upper bound on the total actual cost, and so the worst-case cost of n INCREMENT operations is O(n).

The potential method gives us an easy way to analyze the counter even when it does not start at zero. There are initially b₀ ′s, and after n INCREMENT operations there are b_n 1's, where 0 ≤ b₀, b_n ≤ k. (Recall that k is the number of bits in the counter.) We can rewrite equation (17.3) as

(17.4)

We have ≤ 2 for all 1 ≤ i ≤ n. Since Φ(D₀) = b₀ and Φ(D_n) = b_n, the total actual cost of n INCREMENT operations is

Note in particular that since b₀ ≤ k, as long as k = O(n), the total actual cost is O(n). In other words, if we execute at least n = Ω(k) INCREMENT operations, the total actual cost is O(n), no matter what initial value the counter contains.

Exercises 17.3-1

Suppose we have a potential function Φ such that Φ(D_i) ≥ Φ(D₀) for all i, but Φ(D₀) ≠ = 0. Show that there exists a potential function Φ′ such that Φ′(D₀) = 0, Φ′(D_i) ≥ 0 for all i ≥ 1, and the amortized costs using Φ′ are the same as theamortized costs using Φ.

Exercises 17.3-2

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

Exercises 17.3-3

Consider an ordinary binary min-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.

Exercises 17.3-4

What is the total cost of executing n of the stack operations PUSH, POP, and MULTIPOP, assuming that the stack begins with s₀ objects and finishes with s_n objects?

Exercises 17.3-5

Suppose that a counter begins at a number with b 1's in its binary representation, rather than at 0. Show that the cost of performing n INCREMENT operations is O(n) if n = Ω(b). (Do not assume that b is constant.)

Exercises 17.3-6

Show how to implement a queue with two ordinary stacks (Exercise 10.1-6) so that the amortized cost of each ENQUEUE and each DEQUEUE operation is O(1).

Exercises 17.3-7

Design a data structure to support the following two operations for a set S of integers:

INSERT(S, x) inserts x into set S.

DELETE-LARGER-HALF(S) deletes the largest ⌈S/2⌉ elements from S.

Explain how to implement this data structure so that any sequence of m operations runs in O(m) time.