Amortized Analysis
CS F364 — Design & Analysis of Algorithms | Summer 2026
A stack supports three operations: Push(x), Pop(), and Multipop(k) which pops up to k items. Using the aggregate method, show that any sequence of n operations starting from an empty stack takes O(n) time.
Each element pushed is popped at most once. Over n operations, there can be at most n pushes (and thus at most n pops across all Pop and Multipop calls). Total cost is O(n), so amortized cost per operation is O(1).
In the accounting method, we assign an amortized cost to each operation. For a binary counter increment, we charge 2 rupees per increment. Explain how this covers the actual cost of flipping bits over a sequence of n increments.
Flip a 0 \to 1 costs 1 rupee (paid now) and 1 rupee saved as credit. Flip a 1 \to 0 costs 1 rupee (from saved credit). Each increment flips exactly one 0 \to 1 and some number of trailing 1s \to 0. Total actual cost = (number of bits flipped). Amortized cost = 2 rupees per increment = O(1) per increment.
A binary counter is implemented as an array of k bits. The only operation is Increment(). Using the potential method with potential function \Phi = \text{number of 1-bits}, show that n increments take O(n) time.
- Define the amortized cost formula: \hat{c}_i = c_i + \Phi_i - \Phi_{i-1}.
- Compute \Delta \Phi for an increment that flips t trailing 1s to 0 and one 0 to 1.
- Show \hat{c}_i = O(1).
Increment from k-1 to k flips t_k trailing 1s to 0 and one 0 to 1 (total t_k+1 flips). The number of 1-bits changes: each 1\to 0 decreases count by 1, each 0\to 1 increases by 1. So \Delta\Phi = -(t_k) + 1 = 1 - t_k. Amortized cost:
\hat{c}_k = (t_k+1) + (1 - t_k) = 2.
So each increment has O(1) amortized cost.
A dynamic table doubles in size when full and halves when load factor drops below 1/4. Using the potential method, prove that n insertions and deletions take O(n) amortized time. Choose a suitable potential function.
Define \Phi = 2 \cdot |\text{size} - \text{capacity}/2|. When the table is half-full, \Phi = 0. When it doubles (\text{size} = \text{capacity}), \Phi = \text{size}, paying for copying. When it halves (\text{size} = \text{capacity}/4), \Phi = \text{capacity}/2, also paying for copying. Each insert/delete has O(1) amortized cost.
Consider a queue implemented using two stacks (one for enqueue, one for dequeue). When the dequeue stack is empty, we pop all elements from the enqueue stack and push them onto the dequeue stack. Using amortized analysis, show that any sequence of n enqueue/dequeue operations takes O(n) time.
Each element is pushed onto the enqueue stack once and moved to the dequeue stack at most once (when dequeued). Total pushes/pops per element is at most 3 (push onto enqueue, pop from enqueue, push onto dequeue, pop from dequeue). So n operations cost O(n) total, O(1) amortized per operation.
A dynamic table starts with capacity 1. On each insert, if the array is full, the capacity is multiplied by 3 (tripling). Use the aggregate method to analyze n inserts.
- How many resizings occur after n inserts? List the capacities at each resize.
- What is the total number of elements copied across all resizings?
- Show that n inserts take O(n) total amortized time.
Resizings occur when capacity reaches 1, 3, 9, 27, \dots, 3^{k-1} where k = \lceil \log_3 n \rceil. Number of resizings = O(\log n).
Total copying cost: 1 + 3 + 9 + \cdots + 3^{k-1} = \frac{3^k - 1}{3 - 1} = \frac{3^k - 1}{2} < \frac{3^k}{2} Since 3^{k-1} < n \le 3^k, we have 3^k < 3n, so total copying \le \frac{3n}{2} = O(n).
Each insert itself costs O(1) (adding the element). Total cost = n inserts + O(n) copying = O(n). By the aggregate method, amortized cost per insert is O(1).