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.

Make the potential function be equal to $\sum_{i = 1}^n \lg i$ where $n$ is the size of the min-heap. Then, there is still a cost of $O(\lg n)$ to $\text{INSERT}$, since only an amount of amortization that is $\lg n$ was spent to increase the size of the heap by $1$.

However, the amortized cost of $\text{EXTRACT-MIN}$ is $0$, as all its actual cost is compensated.

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.