16. Amortized Analysis

Exercises

16.1-1

Available in the latest revision of the IM.

16.1-2

Available in the latest revision of the IM.

16.1-3

Available in the latest revision of the IM.

16.2-1

Available in the latest revision of the IM.

16.2-2

Available in the latest revision of the IM.

16.2-3

Available in the latest revision of the IM.

The solution in the IM ignores the cost of reading bits. Namely, the while loop in the INCREMENT operation checks whether A[i] == 1. If we follow the prompt's exact wording and charge $1 for every read and $1 for every write, our accounting must be more precise:

• Every bit flipped to 1 needs $2 in credit attached to it, not $1 (to pay for the future act of reading it as a 1, and the subsequent act of modifying it to 0).

• The operation itself needs to pay $2 just to handle the final 0 bit (reading the 0 to exit the while loop, then modifying it to 1).

Therefore, each INCREMENT should be charged by $6 rather than $4. Of course, this doesn't impact the final conclusion about amortized cost, but emphasizes the need for due diligence when applying the accounting method.

16.3-1

Available in the latest revision of the IM.

16.3-2 🌟

Demonstrates the core rule of designing a potential function: it must be capable of collapsing. In the potential method, a massive drop in potential $\Phi$ is the mathematical equivalent of spending credit in the accounting method. This is why the IM defines $\Phi(D_i) = 2i - 2^{\lfloor \lg i \rfloor + 1}$ for $i > 0$ and $\Phi(D_0)=0$. Try using $\Phi(D_i)=2i$ for $i >0$ and things will fall apart despite $\Phi(D_i) \ge 0$ for all $i > 0$.

Available in the latest revision of the IM.

Reverse-engineering the potential function

Let’s derive the formula $\Phi(D_i) = 2i - 2^{\lfloor \lg i \rfloor + 1}$ for $i > 0$ from the IM.

1

Identify the debt

At step $i = 2^k$, we are going to get hit with a massive bill of $2^k$. We need to pay for this using the potential we saved up during the cheap operations.

2

Calculate the savings rate

The previous expensive operation happened at $i = 2^{k-1}$. The current one is at $i = 2^k$. The number of cheap steps between them is $2^{k-1}$. During this period, we must accumulate enough potential to pay for the next expensive operation. Therefore, we must increase it by 2 at every single cheap step.

3

Translate to formula

$$\Phi(D_i) = 2 \times (\text{items added since the last exact power of 2})=2(i - 2^{\lfloor \lg i \rfloor})= 2i - 2^{\lfloor \lg i \rfloor + 1}.$$

16.3-3 🌟

Illustrates that amortized analysis is rarely used to discover unknown bounds; it is a tool used to justify bounds we already suspect or actively want to design.

The real question is: "What benefits do we get by proving an amortized cost of EXTRACT-MIN to be $O(1)$?" Because we can't extract an item that hasn't been inserted, the total time spent extracting can never exceed the total time spent inserting. By successfully shifting the cost so that INSERT pays for EXTRACT-MIN, we mathematically formalize the idea that the insertion phase is the absolute bottleneck of the data structure. Therefore, amortized analysis simplifies complex algorithm reasoning by focusing on what matters most.

Available in the latest revision of the IM.

16.3-4

Available in the latest revision of the IM.

16.3-5

Available in the latest revision of the IM.

16.3-6

Available in the latest revision of the IM.

16.4-1

Available in the latest revision of the IM.

16.4-2 🌟

Exemplifies the probabilistic amortized analysis by computing the expected value of the amortized cost:

$\mathbb{E}[\hat{c}_i] = \mathbb{E}[c_i] + \Phi(D_i) - \Phi(D_{i-1}).$

Available in the latest revision of the IM.

16.4-3

Available in the latest revision of the IM.

16.4-4

Available in the latest revision of the IM.

Problems

16-1 Binary reflected Gray code

Available in the latest revision of the IM.

16-2 Making binary search dynamic

Available in the latest revision of the IM.

Part (b) in the IM contains a flaw in applying the aggregate method. By strict definition, it computes the total cost of a sequence of $n$ operations and divides by $n$. The defining characteristic of this method is that it assigns the exact same amortized cost to every single operation in the sequence, regardless of the operation type. If we follow the prompt's constraint ("assuming that the only operations are INSERT and SEARCH") and create a sequence of $n/2$ inserts followed by $n/2$ searches, the total time is heavily dominated by the searches: $O(n \lg^2 n)$. Therefore, the aggregate method must conclude that the amortized cost per operation (for the whole sequence) is:

$\frac{O(n \lg^2 n)}{n} = O(\lg^2 n).$

16-3 Amortized weight-balanced trees

a.

The initial call is Rebuild-Subtree(T, x).

Inorder-Store(x, A, k)
1  Fills the array A with node pointers in sorted order and returns the next available index.
2  if x != NIL
3      k = Inorder-Store(x.left, A, k)
4      A[k] = x
5      k = Inorder-Store(x.right, A, k + 1)
6  return k

Build-Balanced(A, i, j)
1  if i > j
2      return NIL
3  mid = ⌊(i + j) / 2⌋
4  root = A[mid] 
5  // Recursively build the left subtree
6  root.left = Build-Balanced(A, i, mid - 1)
7  if root.left != NIL
8      root.left.p = root
9  // Recursively build the right subtree
10 root.right = Build-Balanced(A, mid + 1, j)
11 if root.right != NIL
12     root.right.p = root
13 // Maintain the augmented size attribute     
14 root.size = j - i + 1
15 return root

Rebuild-Subtree(T, x)
1  m = x.size
2  Let A[1 .. m] be a new array
3  Inorder-Store(x, A, 1)
4  parent = x.p
5  y = Build-Balanced(A, 1, m)
6  if parent == NIL
7      T.root = y
8  elseif parent.left == x
9      parent.left = y
10 else parent.right = y
11 y.p = parent

b.

Search takes $O(h)$ worst-case time, where $h$ is the height of a BST. After $h$ steps down the tree, the number of nodes remaining in a subtree is at most $n \alpha^h$. Since the smallest possible subtree has 1 node (a leaf), we have:

$$n \alpha^h \ge 1 \implies h \le \log_{1/\alpha} n = O(\lg n).$$

Therefore, performing a search in an $n$-node α-balanced binary search tree takes $O(\lg n)$ worst-case time.

c.

By definition, $\Delta(x) \ge 0$ for all $x$, thus any BST has nonnegative potential (assuming that the constant multiplier $c$ is positive). A 1/2-balanced tree is, in a sense, as balanced as it can be. Therefore, it has $\Delta(x) \le 1$ for all $x$. This entails that a 1/2-balanced tree has potential 0.

d.

To determine how large the constant $c$ must be, we need to ensure that the drop in the potential function $\Phi$ during a rebuild is large enough to completely pay for the $m$ units of actual work required to rebuild the $m$-node subtree.

A rebuild is triggered exactly when a node $x$ (where $x.size = m$) ceases to be $\alpha$-balanced. This happens when an insertion (or symmetrically deletion) pushes the size of its heavier child strictly above the threshold $\alpha m$. Let the heavier child's size be $h$. We know $h > \alpha m$. Let the lighter child's size be $l$. Because the total size is $m$ and the root $x$ itself counts as 1 node, $l = m - 1 - h$. Now, let's calculate the size difference $\Delta(x)$ for this node at the exact moment the threshold is crossed:

$$\Delta(x) = h - l= 2h - m + 1 \implies \Delta(x) > m(2\alpha - 1) + 1. \approx m(2\alpha - 1).$$

Before the rebuild, the potential at node $x$ alone is $c \cdot \Delta(x)$. After the rebuild, the entire subtree is 1/2-balanced. As we proved previously, a 1/2-balanced tree has a potential of exactly 0. Furthermore, rebuilding the subtree rooted at $x$ does not change the sizes of any ancestors of $x$, so their potentials remain untouched. Therefore, the total drop in potential in the system is at least the potential that was stored at $x$. We need to ensure

$$\hat c_i =c_i+\Delta(\Phi_i) =m-cm(2\alpha-1) \le 0 \implies c \ge \frac{1}{2\alpha - 1}.$$

Because $\alpha > 1/2$, the denominator $(2\alpha - 1)$ is always a strictly positive fraction. If $\alpha$ is close to 1/2 (meaning the tree is kept very strictly balanced), then it forces $c$ to be very large—we have to aggressively save a lot of potential during regular operations to pay for the frequent, inevitable rebuilds!

e.

Inserting a node into or deleting a node from an n-node α-balanced tree costs $O(\lg n)$ time in the worst-case. If such an operation triggers a rebalancing action, then by part (d), we know that rebuilding a subtree to make it 1/2-balanced takes $O(1)$ amortized time.

Because the tree is $\alpha$-balanced before the operation, its height is strictly $O(\lg n)$. Therefore, there are at most $O(\lg n)$ ancestors on the search path for a new slot or toward the node to be deleted. For any ancestor on this path, the size of exactly one of its subtrees (either left or right) changes by exactly 1. The other subtree remains unchanged. Since the potential function is $\Phi(T) = c \sum \Delta(x)$, each node on the path contributes at most $c \cdot 1$ to the new potential. With $O(\lg n)$ nodes involved, the total maximum increase in the tree's potential is $c \cdot O(\lg n) = O(\lg n)$.

Therefore, inserting a node into or deleting a node from an $n$-node α-balanced tree costs $O(\lg n)$ amortized time.

16-4 The cost of restructuring red-black trees

Available in the latest revision of the IM.