Exercises — Amortized analysis — aggregate, accounting, potential methods

This is the Aggregate method. Why: the defining move is computing $T(m)$ directly as one lump and reporting $T(m)/m$ identically for every operation. Weakness: because it hands every operation the same amortized cost, it is weak when different operation types have genuinely different amortized behaviour (e.g. a structure with both cheap find and expensive delete) — it can't distinguish them.

They broke requirement 1: $\Phi (D_0)=0$ (the empty start must have zero stored energy). A negative starting potential means the amortized total could undershoot the real total, so the bound would be dishonest. (It also violates $\Phi \ge 0$.)

(a) Copy work. Copies happen when size crosses $1,2,4,\dots$ The last power of two $\le 1000$ is $512=2^9$. Copy costs sum to $1+2+4+\cdots +512=2^{10}-1=1023<2m=2000.✓$ So total copy work is exactly $1023$. (b) Total work $T(m)=\underset{\text{writes}}{\underbrace{1000}}+\underset{\text{copies}}{\underbrace{1023}}=2023$. Amortized $=2023/1000=2.023\le 3=O(1)$. Why the "3": even in the loosest bound $T(m)<m+2m=3m$, so $\hat{c}<3$ always.

Direct count. Bit $b_0$ (least significant) flips every increment: $16$ times. Bit $b_1$ flips every 2 increments: $8$. Bit $b_2$: every 4: $4$. Bit $b_3$: every 8: $2$. Bit $b_4$: every 16: $1$. $\text{total flips}=16+8+4+2+1=31.$ Check the charge: $\hat{c}\cdot n=2\cdot 16=32\ge 31$. ✓ The bank stays solvent. Why it works: every 0→1 flip prepays its own future 1→0 flip. In general total flips over $n$ increments $={\sum }_{j\ge 0}\lfloor n/2^j\rfloor <2n$ — the geometric tail again.

Actual cost $c_i=1$ (write one element). Potential change: $\Delta \Phi =(2(n+1)-s)-(2n-s)=2.$ ${\hat{c}}_i=c_i+\Delta \Phi =1+2=3.$ Why: the push does $1$ unit of real work but deposits $2$ units of stored energy for the copy that is coming. Amortized $=3=O(1)$.

Actual cost $c_i=n+1$ (copy $n$ + insert $1$).

• Before (full): ${\Phi }_{\text{before}}=2n-s=2n-n=n$.
• After (doubled): ${\Phi }_{\text{after}}=2(n+1)-2s=2(n+1)-2n=2$. $\Delta \Phi =2-n,{\hat{c}}_i=(n+1)+(2-n)=3.$ What cancels: the giant real cost $n+1$ is annihilated by the potential dropping by $n-2$. The stored energy pays the copy, leaving $\hat{c}=3$. See the picture below — the red bar (potential) collapses exactly as the copy fires.

If $n<s/2$ then $2n<s$, so $2n-s<0$ — the potential goes negative, violating requirement $\Phi \ge 0$. A negative potential means we might be "borrowing" energy we never stored, and the amortized total could fall below the real total → dishonest bound. The real fix: structures that also shrink use a two-piece potential, e.g. $\Phi =\{\begin{array}{ll}2n-s& n\ge s/2\\ \frac{s}{2}-n& n<s/2\end{array}$ so that potential rises again as the table empties, ready to pay for a shrink copy. Below $s/2$, each pop deposits energy for the eventual halving. The figure shows both wings.

Requirements: $\Phi (D_0)=0$ (empty) ✓ and $\Phi \ge 0$ (a count) ✓. Push ($n\to n+1$): $c_i=1$, $\Delta \Phi =+1$, so $\hat{c}=1+1=2$. Multipop popping $p=\min (k,n)$ elements: $c_i=p$, but $\Delta \Phi =-p$ (stack shrinks by $p$). So $\hat{c}=p+(-p)=0.$ Every operation has amortized cost $\le 2=O(1)$. Why it works: you can only pop what you pushed; each element's pop was prepaid by the $+1$ stored at its push. A multipop of $1000$ elements looks expensive but its real cost is exactly cancelled by the potential it releases.

Choose $\Phi =2\cdot (\text{size of In})$. Check: $\Phi (D_0)=0$ ✓, $\Phi \ge 0$ ✓. Enqueue (push to In): $c_i=1$, $\Delta \Phi =+2$, so $\hat{c}=1+2=3$. Dequeue with Out non-empty: $c_i=1$ (one pop), $\Delta \Phi =0$, $\hat{c}=1$. Dequeue triggering a flip of $j$ elements: $c_i=j(\text{pop In})+j(\text{push Out})+1(\text{pop Out})=2j+1$. In empties, so $\Delta \Phi =-2j$. Then $\hat{c}=(2j+1)+(-2j)=1.$ Every operation is $O(1)$ amortized. Why the factor 2: each enqueued element will later be moved twice (popped from In, pushed to Out), so we bank $2$ units at enqueue time to prepay exactly that.

Design. Let $\Phi =(\text{number of currently-set slots})$. Check: $\Phi (D_0)=0$ ✓, $\Phi \ge 0$ ✓. SET on an unset slot: $c_i=1$, $\Delta \Phi =+1\Rightarrow \hat{c}=2$. SET on an already-set slot (idempotent, no state change): $c_i=1$, $\Delta \Phi =0\Rightarrow \hat{c}=1$. RESET clearing $r$ set slots: $c_i=r$, $\Delta \Phi =-r\Rightarrow \hat{c}=r+(-r)=0$. Both $\le 2=O(1)$. Each set slot stored $+1$ at its SET, released to pay its own clear. Degenerate RESET on empty structure: $r=0$, so $c_i=0$, $\Delta \Phi =0$, $\hat{c}=0$. No underflow, potential never negative — the bound survives the empty case cleanly.

All three methods bound the same quantity: ${\sum }_{i=1}^m{\hat{c}}_i\ge T(m)=\sum c_i$, and each reports a valid upper bound on $T(m)$.

• Aggregate computes $T(m)$ itself and sets ${\hat{c}}_i=T(m)/m$ for all $i$: total $=T(m)$.
• Accounting requires the bank $\sum ({\hat{c}}_i-c_i)\ge 0$, i.e. $\sum {\hat{c}}_i\ge T(m)$.
• Potential gives $\sum {\hat{c}}_i=T(m)+\Phi (D_m)-\Phi (D_0)\ge T(m)$ since $\Phi (D_m)\ge \Phi (D_0)$. All three satisfy the same inequality $\sum {\hat{c}}_i\ge T(m)$. The real total work $T(m)$ is a physical fact — it doesn't depend on our bookkeeping. What differs is only how each method distributes $T(m)$ (plus leftover credit/potential) across the $m$ operations. Given the tightest choices ($\Phi (D_m)=\Phi (D_0)$, zero leftover credit), they collapse to the identical bound $T(m)/m$. Bookkeeping cannot change reality.

The three methods are three ways to pay a bill you already owe. The bill ($T(m)$) is fixed by physics. Aggregate = pay the lump sum and split evenly. Accounting = put coins in a jar per element. Potential = track the "stored energy" of the whole structure. Every jar-of-coins or energy trick must, when you cash out, cover the same real bill — so all three land on the same $O(1)$ per operation.