Exercises — Amortized O(1) operations

(a) Cheap writes contribute $n$. The spikes $2+4+8+\cdots +2^m<2n$ (geometric sum). Total $<3n=O(n)$ → amortized $O(1)$. ✅ (b) Total $=1+2+\cdots +n=\frac{n(n+1)}{2}=O(n^2)$ → amortized $=\frac{n(n+1)/2}{n}=\frac{n+1}{2}=O(n)$ → NOT constant. ❌ (c) Total $=5n=O(n)$ → amortized $=5=O(1)$. ✅ (Being expensive every time is fine as long as the cost is a constant.)

What we did: summed each sequence and divided by $n$. Why: amortized cost is literally total$/n$.

False. A dynamic-array resize is genuinely $O(n)$, yet the sequence is still amortized $O(1)$. A rare $O(n)$ spike is allowed — what matters is that the total stays $O(n)$. The whole point of amortization is to permit occasional expensive ops.

A resize triggers when the array is already full and we push one more.

Total $=1+2+3+1+5+1+1+1=15$. Amortized $=15/8=1.875\le 3$. ✅ Check with the formula: copies $=1+2+4=7$, writes $=8$, total $=15$. Matches.

Using $\alpha =\text{size}/\text{capacity}\le 0.5$, the largest size allowed at capacity $C$ is $0.5C$. Rehash fires when the next insert would exceed it.

• cap 4 allows size up to $0.5\times 4=2$ → insert 3rd: rehash to cap 8, copy 2.
• cap 8 allows up to 4 → insert 5th: rehash to cap 16, copy 4.
• cap 16 allows up to 8 → insert 9th: rehash to cap 32, copy 8.
• cap 32 allows up to 16 → insert 17th: rehash to cap 64, copy 16.
• cap 64 allows up to 32 → we stop at 20 items, no more rehash.

Capacities: $4\to 8\to 16\to 32\to 64$. Total copy cost $=2+4+8+16=30$. Inserts done to go from 2 to 20 items $=18$ writes. Total $=30+18=48$; amortized $=48/18\approx 2.67\le 3$. ✅

With chunk size $c$, resizes happen at sizes $c,2c,3c,\dots$ Taking $n$ a multiple of $c$ for cleanliness (rounding changes nothing asymptotically — see the note below), there are exactly $n/c$ resizes, and the $k$-th resize copies $kc$ elements. $\text{copy cost}={\sum }_{k=1}^{n/c}kc=c\cdot \frac{(n/c)(n/c+1)}{2}=\frac{n(n+c)}{2c}$ For large $n$ this is $\approx \frac{n^2}{2c}=O(n^2)$. Amortized $=O(n)$. ❌ On the rounding: for general $n$ the number of resizes is $\lfloor n/c\rfloor$, so the true copy cost is $\frac{\lfloor n/c\rfloor (\lfloor n/c\rfloor +1)}{2}c$. Since $\lfloor n/c\rfloor$ differs from $n/c$ by less than $1$, this changes the sum by only $O(n)$ — negligible against the $\Theta (n^2)$ leading term. The floor never rescues the quadratic. Why: this is an arithmetic series ($1+2+3+\dots$), which grows quadratically. Making $c$ bigger only shrinks the constant $\frac{1}{2c}$ — it never removes the $n^2$. You need geometric growth to kill the square.

Setup — how many resizes? Let the capacities reached be $c_0=1,c_1,c_2,\dots ,c_M$ where $c_i=\lceil r{c}_{i-1}\rceil$, and $c_M$ is the last one needed to hold $n$ items. Because each capacity is at least $r$ times the previous, $c_i\ge r^i$, so the last exponent satisfies $r^M\le c_M$ and there are $M+1=O(\log n)$ resizes. Precisely, since $c_i\ge r^i$ and we stop once capacity $\ge n$, the number of resizes is $M=\lfloor {\log }_{r}n\rfloor$ at most — the largest exponent with $r^M\le n$ — which is exactly why $M+1=O(\log n)$. Keep that "$\log$" in mind; it becomes a harmless correction term.

Bounding each capacity (the rounding must be tracked carefully). The ceiling adds at most $1$ per step, and those errors compound, so we cannot claim $c_i<r^i+1$. Instead unroll the recurrence $c_i=\lceil r{c}_{i-1}\rceil <r{c}_{i-1}+1$: $c_i<r{c}_{i-1}+1<r(r{c}_{i-2}+1)+1=r^2{c}_{i-2}+r+1<\cdots <r^i{c}_0+(r^{i-1}+r^{i-2}+\cdots +1).$ With $c_0=1$ the tail is itself a geometric sum $\frac{r^i-1}{r-1}$, giving the honest bound $c_i<r^i+\frac{r^i-1}{r-1}=r^i(1+\frac{1}{r-1})-\frac{1}{r-1}=r^i\cdot \frac{r}{r-1}-\frac{1}{r-1}.$ So the accumulated rounding error is not a constant $+1$; it is absorbed into the same $\frac{r}{r-1}$ factor — the capacities are at most a constant multiple of $r^i$.

Summing the copy cost. The copy cost at capacity $c_i$ is $c_i$, so $\text{copy cost}={\sum }_{i=0}^M{c}_i<\frac{r}{r-1}{\sum }_{i=0}^M{r}^i=\frac{r}{r-1}\cdot \frac{r^{M+1}-1}{r-1}.$ Since $r^M\le n$ we have $r^{M+1}\le rn$, so $\text{copy cost}<\frac{r}{r-1}\cdot \frac{rn}{r-1}=\frac{r^2}{(r-1{)}^2}n.$ That is already linear. A tighter bound recovers the clean constant: the dominant geometric sum $\sum r^i=\frac{r^{M+1}-1}{r-1}<\frac{rn}{r-1}$ contributes copy cost $<\frac{rn}{r-1}$, and the accumulated rounding contributes only the smaller-order $O(r^M)+O(M)=O(n/\text{const})$ tail plus the $O(\log n)$ resize count — both lower order after dividing by $n$.

Divide by $n$. The leading term gives amortized copy cost per push ${\lim }_{n\to \infty }\frac{1}{n}\cdot \frac{rn}{r-1}=\frac{r}{r-1},$ because every correction term (the compounded rounding, the $O(\log n)$ resize count) is lower order and washes out in the limit. Adding the $1$ per write gives total amortized $1+\frac{r}{r-1}$.

• $r=2$: copy part $=\frac{2}{2-1}=2$ → total $3$. Matches the parent note's "3." ✅
• $r=1.5$: copy part $=\frac{1.5}{0.5}=3$ → total $4$. Slower per-op, but still $O(1)$ — and it wastes less memory.

The next figure plots this constant $\frac{r}{r-1}$ against the growth factor $r$ so you can see how the choice of $r$ trades speed against memory:

Reading the curve (refer to the figure above): the cyan curve is $\frac{r}{r-1}$. As $r\to 1^{+}$ (left edge) it shoots up toward infinity — this is the amber-annotated "approaching additive growth" bad case, exactly the $O(n)$ disaster of Exercise 3.1. Moving right, the amber dot at $r=2$ sits at cost $2$, and as $r$ grows further the cost sinks toward $1$ but memory waste (empty slots) rises. $r=2$ is the popular compromise: cheap enough, wastes at most half the table.

Amortized cost $=\text{actual cost}+\Delta \Phi$, where $\Delta \Phi ={\Phi }_{\text{after}}-{\Phi }_{\text{before}}$. Summing over the run, total amortized $=$ total actual $+({\Phi }_{\text{final}}-{\Phi }_{\text{initial}})$. For amortized costs to upper-bound the real total we need ${\Phi }_{\text{final}}\ge {\Phi }_{\text{initial}}$ — so we must pin down ${\Phi }_{\text{initial}}$ and show $\Phi$ never dips below it.

(a) Fixing the starting point. The empty-array corner does look bad: at size $0$, capacity $1$, $\Phi =2\cdot 0-1=-1$. So the naive claim "$\Phi \ge 0$ always" is false at the very start — this is the subtlety the method demands we handle. Two standard, equivalent fixes:

• Fix 1 (shift the baseline). Take ${\Phi }_{\text{initial}}=-1$ as the reference value. All we need is that $\Phi$ never goes below its initial value $-1$. Once the first element is added the array is full-or-fuller and $\Phi \ge 0>-1$ forever after, so indeed $\Phi \ge {\Phi }_{\text{initial}}$ for the whole run. The constant offset ${\Phi }_{\text{final}}-{\Phi }_{\text{initial}}$ adds only $O(1)$ to the total — it does not affect the amortized bound.
• Fix 2 (start at capacity 1 already reserved, or define $\Phi =\max (0,2\cdot \text{size}-\text{capacity})$). Then ${\Phi }_{\text{initial}}=0$ and $\Phi \ge 0$ throughout by construction.

Either way the prerequisite "$\Phi \ge {\Phi }_{\text{initial}}$ at all times" holds, so the amortized costs below are a genuine upper bound. From the first non-empty state onward, "at least half full" means $\text{size}\ge \frac{1}{2}\text{capacity}$, i.e. $2\cdot \text{size}\ge \text{capacity}$, so $\Phi =2\cdot \text{size}-\text{capacity}\ge 0$. Right after a doubling the array is exactly half full ($\Phi =2$), and $\Phi$ only rises as we add.

(b) Cheap push (room exists): actual $=1$ (one write). Size $+1$, capacity unchanged → $\Delta \Phi =2(\text{size}+1)-2\cdot \text{size}=2$. Amortized $=1+2=3$. ✅

(c) Resize push: before, $\text{size}=m=\text{capacity}=m$ (array full). Actual cost $=m$ copies $+1$ write $=m+1$. After, size $=m+1$, capacity $=2m$. ${\Phi }_{\text{before}}=2m-m=m,{\Phi }_{\text{after}}=2(m+1)-2m=2.$ $\Delta \Phi =2-m$. Amortized $=(m+1)+(2-m)=3$. ✅ The $+m$ copy cost is exactly cancelled by the $-m$ drop in potential — the "saved work" gets spent.

Both cases give exactly 3 → amortized $O(1)$, no averaging, no probability.

Accounting idea. Each element can be popped at most once, and it must have been pushed before it can be popped. We use these two facts to design charges that never let the credit bank go negative.

The charging scheme.

• Charge each push ₹2 (2 units): ₹1 pays for the actual push (the real work), and ₹1 is stored as credit on that specific element.
• Charge each multipop ₹0 up front: when it removes an element, that element's pop is paid by the ₹1 of credit sitting on it.

Why the bank never goes negative (the key invariant, now proved). Define $\text{credit}=$ number of elements currently on the stack, since exactly ₹1 of credit is deposited on each element when it is pushed and that ₹1 is still there until the element is popped. This credit is always the stack's current size, which is $\ge 0$ by definition — you cannot have a negative number of items. Concretely:

• A push adds one element and deposits its ₹1 → credit rises by 1, stays $\ge 0$.
• A multipop(k) removes $p=\min (k,\text{size})$ elements, spending exactly $p$ units of credit — one from each removed element. Since it removes only elements that are present (each of which carries its own ₹1), it never spends credit that isn't there. Credit drops by $p$ but stays $\ge 0$ because $p\le \text{size}=\text{credit}$.

So at every moment $\text{credit}=\text{size}\ge 0$: the invariant holds, the accounting is honest.

The bound. Total money charged $=$ (₹2 per push) $+$ (₹0 per multipop) $\le 2\times (\text{number of pushes})\le 2n$. Because the charges never undercharge (credit never went negative), the real total cost $\le$ total charged $\le 2n=O(n)$. Amortized cost per operation $\le \frac{2n}{n}=2=O(1)$, even though a single multipop can be $O(n)$.

Why the same trick works: like resizing, a big op (multipop) only removes work that was individually pre-paid by cheap ops (push). This is the exact same "pay it forward" as charging 3 units per array push.

Fill the array to exactly capacity $=m$ (size $=m$). Now alternate:

• push → size $m+1>m$ = full → double to cap $2m$, copy $m$. Cost $\approx m$.
• pop → size back to $m=\frac{1}{2}(2m)$ → halve to cap $m$, copy $m$. Cost $\approx m$.
• push → full again → double, copy $m$… and so on.

Every single operation triggers a full $O(m)$ copy. Over $n$ such ops, total $=\Theta (nm)=\Theta (n^2)$ → amortized $\Theta (n)$. ❌ The structure oscillates across the resize boundary — it's stuck at the worst possible spot.

The fix — hysteresis: grow at load $1$ (double when full) but shrink only when size drops to $\frac{1}{4}$ capacity (halve then). This leaves a gap between the grow and shrink thresholds, so after any resize the array is exactly half full and needs $\Theta (m)$ more cheap ops before the next resize can fire. The geometric argument (and a potential like $\Phi =|2\cdot \text{size}-\text{capacity}|$) then restores amortized $O(1)$.

From Exercise 3.2, amortized copy cost $=\frac{r}{r-1}$ with $r=\varphi =1.618\dots$: $\frac{\varphi }{\varphi -1}=\frac{1.618}{0.618}\approx \mathrm{2.618.}$ Total amortized per push $\approx 1+2.618=3.618=O(1)$. ✅ One-line reason: for any $r>1$ the copy sum is a convergent-ratio geometric series, so it's bounded by the finite constant $\frac{r}{r-1}$ times $n$ — the exponent stays 1, never 2. Only $r\to 1$ breaks it.

(Fun fact: since $\varphi$ satisfies ${\varphi }^2=\varphi +1$, dividing by $\varphi$ gives $\varphi =1+\frac{1}{\varphi }$, i.e. $\varphi -1=\frac{1}{\varphi }$. Hence $\frac{\varphi }{\varphi -1}=\varphi \cdot \varphi ={\varphi }^2=\varphi +1\approx 2.618$. So golden-ratio copy cost equals ${\varphi }^2$.)