# 17.3 The potential method

## 17.3-1

Suppose we have a potential function $\Phi$ such that $\Phi(D_i) \ge \Phi(D_0)$ for all $i$, but $\Phi(D_0) \ne 0$. Show that there exists a potential fuction $\Phi'$ such that $\Phi'(D_0) = 0$, $\Phi'(D_i) \ge 0$ for all $i \ge 1$, and the amortized costs using $\Phi'$ are the same as the amortized costs using $\Phi$.

Define the potential function $\Phi'(D_i) = \Phi(D_i) - \Phi(D_0)$ for all $i \ge 1$.

Then

$$\Phi'(D_0) = \Phi(D_0) - \Phi(D_0) = 0,$$

and

$$\Phi'(D_i) = \Phi(D_i) - \Phi(D_0) \ge 0.$$

The amortized cost is

$$ \begin{aligned} \hat c_i' & = c_i + \Phi'(D_i) - \Phi'(D_{i - 1}) \\ & = c_i + (\Phi(D_i) - \Phi(D_0)) - (\Phi(D_{i - 1}) - \Phi(D_0)) \\ & = c_i + \Phi(D_i) - \Phi(D_{i - 1}) \\ & = \hat c_i. \end{aligned} $$

## 17.3-2

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

Define the potential function $\Phi(D_0) = 0$, and $\Phi(D_i) = 2i - 2^{1 + \lfloor \lg i \rfloor}$ for $i > 0$. For operation 1,

$$\hat c_i = c_i + \Phi(D_i) - \Phi(D_{i - 1}) = 1 + 2i - 2^{1+ \lfloor \lg i \rfloor} - 0 = 1.$$

For operation $i(i > 1)$, if $i$ is not a power of $2$, then

$$\hat c_i = c_i + \Phi(D_i) - \Phi(D_{i - 1}) = 1 + 2i - 2^{1 + \lfloor \lg 1 \rfloor} - (2(i - 1) - 2^{1 + \lfloor \lg(i - 1) \rfloor}) = 3.$$

If $i = 2^j$ for some $j \in \mathbb N$, then

$$\hat c_i = c_i + \Phi(D_i) - \Phi(D_{i - 1}) = i + 2i - 2^{1 + j}-(2(i - 1) - 2^{1 + j - 1}) = i + 2i - 2i - 2i + 2 + i = 2.$$

Thus, the amortized cost is $3$ per operation.

## 17.3-3

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

Let $D_i$ be the heap after the $i$th operation, and let $D_i$ consist of $n_i$ elements. Also, let $k$ be a constant such that each $\text{INSERT}$ or $\text{EXTRACT-MIN}$ operation takes at most $k \ln n$ time, where $n = \max(n_{i - 1}, n_i)$. (We don't want to worry about taking the log of $0$, and at least one of $n_{n - 1}$ and $n_i$ is at least $1$. We'll see later why we use the natural log.)

Define

$$ \Phi(D_i) = \begin{cases} 0 & \text{if $n_i = 0$}, \\ k n_i \ln n_i & \text{if $n_i > 0$}. \end{cases} $$

This function exhibits the characteristics we like in a potential function: if we start with an empty heap, then $\Phi(D_0) = 0$, and we always maintain that $\Phi(D_i) \ge 0$.

Before proving that we achieve the desired amortized times, we show that if $n \ge 2$, then $n \ln\frac{n}{n - 1} \le 2$. We have

$$ \begin{aligned} n \ln\frac{n}{n - 1} & = n\ln \Big(1 + \frac{1}{n - 1} \Big) \\ & = \ln \Big(1 + \frac{1}{n - 1} \Big)^n \\ & \le \ln\big(e^{\frac{1}{n - 1}} \big)^n & \text{(since $1 + x \le e^x$ for all real $x$)} \\ & = \ln e^{\frac{n}{n - 1}} \\ & = \frac{n}{n - 1} \\ & \le 2, \end{aligned} $$

assuming that $n \ge 2$. (The equation $\ln e^{\frac{n}{n - 1}} = \frac{n}{n - 1}$ is why we use the natural log.) If the $i$th operation is an $\text{INSERT}$, then $n_i = n_{i - 1} + 1$. If the $i$th operation inserts into an empty heap, then $n_i = 1$, $n_{i - 1} = 0$ and the amortized cost is

$$ \begin{aligned} \hat c_i & = c_i + \Phi(D_i) - \Phi(D_{i - 1}) \\ & \le k\ln 1 + k \cdot 1\ln 1 - 0 \\ & = 0. \end{aligned} $$

If the $i$th operation inserts into a nonempty heap, then $n_i = n_{i - 1} + 1$, and the amortized cost is

$$ \begin{aligned} \hat c_i & = c_i + \Phi(D_i) - \Phi(D_{i - 1}) \\ & \le k\ln n_i + k n_i\ln n_i - k n_{i - 1}\ln n_{i - 1} \\ & = k\ln n_i + k n_i\ln n_i - k(n_i - 1) \ln(n_i - 1) \\ & = k\ln n_i + k n_i\ln n_i - kn_i\ln(n_i - 1) + k\ln(n_i - 1) \\ & < 2k\ln n_i + kn_i \ln\frac{n_i}{n_i - 1} \\ & \le 2k\ln n_i + 2k \\ & = O(\lg n_i). \end{aligned} $$

If the $i$th operation is an $\text{EXTRACT-MIN}$, then $n_i = n_{i - 1} - 1$. If the $i$th operation extracts the one and only heap item, then $n_i = 0$, $n_{i - 1} = 1$, and the amortized cost is

$$ \begin{aligned} \hat{c_i} & = c_i + \Phi(D_i) - \Phi(D_{i - 1}) \\ & \le k\ln 1 + 0 - k \cdot 1\ln 1 \\ & = 0. \end{aligned} $$

If the $i$th operation extracts from a heap with more than 1 item, then $n_i = n_{i - 1} - 1$, and $n_{i - 1} \ge 2$, and the amortized cost is

$$ \begin{aligned} \hat c_i & = c_i + \Phi(D_i) - \Phi(D_{i - 1}) \\ & \le k\ln n_{i - 1} + kn_i\ln n_i - kn_{i - 1}\ln n_{i - 1} \\ & = k\ln n_{i - 1} + k(n_{i - 1} - 1)\ln(n_{i - 1} - 1) - kn_{i - 1}\ln n_{i - 1} \\ & = k\ln n_{i - 1} + kn_{i - 1}\ln(n_{i - 1} - 1) - k\ln(n_{i - 1} - 1) - kn_{i - 1}\ln n_{i - 1} \\ & = k\ln\frac{n_{i - 1}}{n_{i - 1} - 1} + kn_{i - 1}\ln\frac{n_{i - 1} - 1}{n_{i - 1}} \\ & < k\ln\frac{n_{i - 1}}{n_{i - 1} - 1} + kn_{i - 1}\ln 1 \\ & = k\ln\frac{n_{i - 1}}{n_{i - 1} - 1} \\ & \le k\ln 2 \qquad \text{(since $n_{i - 1} \ge 2$)} \\ & = O(1). \end{aligned} $$

A slightly different potential function—which may be easier to work with—is as follows. For each node $x$ in the heap, let $d_i(x)$ be the depth of $x$ in $D_i$ . Define

$$ \begin{aligned} \Phi(D_i) & = \sum_{x\in D_i} k(d_i(x) + 1) \\ & = k \Bigg(n_i + \sum_{x\in D_i} d_i(x) \Bigg), \end{aligned} $$

where $k$ is defined as before.

Initially, the heap has no items, which means that the sum is over an empty set, and so $\Phi(D_0) = 0$. We always have $\Phi(D_i) \ge 0$, as required.

Observe that after an $\text{INSERT}$, the sum changes only by an amount equal to the depth of the new last node of the heap, which is $\lfloor \lg n_i \rfloor$. Thus, the change in potential due to an $\text{INSERT}$ is $k(1 + \lfloor \lg n_i \rfloor)$, and so the amortized cost is $O(\lg n_i) + O(\lg n_i) = O(\lg n_i) = O(\lg n)$.

After an $\text{EXTRACT-MIN}$, the sum changes by the negative of the depth of the old last node in the heap, and so the potential *decreases* by $k(1 + \lfloor \lg n_{i - 1} \rfloor)$. The amortized cost is at most $k\lg n_{i - 1} - k(1 + \lfloor \lg n_{i - 1} \rfloor) = O(1)$.

## 17.3-4

What is the total cost of executing $n$ of the stack operations $\text{PUSH}$, $\text{POP}$, and $\text{MULTIPOP}$, assuming that the stack begins with $s_0$ objects and finishes with $s_n$ objects?

Let $\Phi$ be the potential function that returns the number of elements in the stack. We know that for this potential function, we have amortized cost $2$ for $\text{PUSH}$ operation and amortized cost $0$ for $\text{POP}$ and $\text{MULTIPOP}$ operations.

The total amortized cost is

$$\sum_{i = 1}^n \hat c_i = \sum_{i = 1}^n c_i + \Phi(D_n) - \Phi(D_0).$$

Using the potential function and the known amortized costs, we can rewrite the equation as

$$ \begin{aligned} \sum_{i = 1}^n c_i & = \sum_{i = 1}^n \hat c_i + \Phi(D_0) - \Phi(D_n) \\ & = \sum_{i = 1}^n \hat c_i + s_0 - s_n \\ & \le 2n + s_0 - s_n, \end{aligned} $$

which gives us the total cost of $O(n + (s_0 - s_n))$. If $s_n \ge s_0$, then this equals to $O(n)$, that is, if the stack grows, then the work done is limited by the number of operations.

(Note that it does not matter here that the potential may go below the starting potential. The condition $\Phi(D_n) \ge \Phi(D_0)$ for all $n$ is only required to have $\sum_{i = 1}^n \hat c_i \ge \sum_{i = 1}^n c_i$, but we do not need for that to hold in this application.)

## 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$ $\text{INCREMENT}$ operations is $O(n)$ if $n = \Omega(b)$. (Do not assume that $b$ is constant.)

$$ \begin{aligned} \sum_{i = 1}^n c_i & = \sum_{i = 1}^n \hat c_i - \Phi(D_n) + \Phi(D_0) \\ & = n - x + b \\ & \le n - x + n \\ & = O(n). \end{aligned} $$

## 17.3-6

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

We'll use the accounting method for the analysis. Assign cost $3$ to the $\text{ENQUEUE}$ operation and $0$ to the $\text{DEQUEUE}$ operation. Recall the implementation of 10.1-6 where we enqueue by pushing on to the top of stack 1, and dequeue by popping from stack 2.

If stack 2 is empty, then we must pop every element from stack 1 and push it onto stack 2 before popping the top element from stack 2. For each item that we enqueue we accumulate 2 credits. Before we can dequeue an element, it must be moved to stack 2. Note: this might happen prior to the time at which we wish to dequeue it, but it will happen only once overall. One of the 2 credits will be used for this move. Once an item is on stack 2 its pop only costs $1$ credit, which is exactly the remaining credit associated to the element. Since each operation's cost is $O(1)$, the amortized cost per operation is $O(1)$.

## 17.3-7

Design a data structure to support the following two operations for a dynamic multiset $S$ of integers, which allows duplicate values:

$\text{INSERT}(S, x)$ inserts $x$ into $S$.

$\text{DELETE-LARGER-HALF}(S)$ deletes the largest $\lceil |S| / 2 \rceil$ elements from $S$.

Explain how to implement this data structure so that any sequence of $m$ $\text{INSERT}$ and $\text{DELETE-LARGER-HALF}$ operations runs in $O(m)$ time. Your implementation should also include a way to output the elements of $S$ in $O(|S|)$ time.

We'll store all our elements in an array, and if ever it is too large, we will copy all the elements out into an array of twice the length.

To delete the larger half, we first find the element $m$ with order statistic $\lceil |S| / 2 \rceil$ by the algorithm presented in section 9.3. Then, scan through the array and copy out the elements that are smaller or equal to $m$ into an array of half the size.

Since the delete half operation takes time $O(|S|)$ and reduces the number of elements by $\lfloor |S| / 2 \rfloor \in \Omega(|S|)$, we can make these operations take ammortized constant time by selecting our potential function to be linear in $|S|$.

Since the insert operation only increases $|S|$ by one, we have that there is only a constant amount of work going towards satisfying the potential, so the total ammortized cost of an insertion is still constant. To output all the elements just iterate through the array and output each.