Question bank — Amortized analysis — aggregate, accounting, potential methods

False. There is no randomness; amortized cost is a guaranteed worst-case average over any sequence — see Big-O, Big-Omega, Big-Theta for the asymptotic bound it produces.

False. One operation may cost $O(n)$ actually (e.g. a doubling copy); "amortized $O(1)$" only bounds the total $T(m)\le m\cdot O(1)$ across the sequence.

False. Average-case is an expectation over a random distribution of inputs; amortized is a deterministic guarantee with no probability at all.

False. All three upper-bound the same real total $T(m)$; they differ only in how you account, not in the answer.

False. You need $\Phi (D_i)\ge 0$ and typically $\Phi (D_0)=0$; the potential is supposed to grow and shrink, just never go negative below the start.

True. Any $\hat{c}$ with $\sum {\hat{c}}_i\ge \sum c_i$ is honest; $5\ge 3$ overcharges but never lies. It is just looser (a weaker $O(1)$ constant).

False. The bank must stay $\ge 0$ at all times; a moment of negative credit means some operation was undercharged and the bound is invalid.

True. Whatever $k$ is, each element is pushed once and popped at most once, so summed pops $\le$ summed pushes; aggregate cost over $m$ ops is $O(m)$, i.e. $O(1)$ amortized.

False. $\Phi$ maps a state to any real number; only $\Phi \ge 0$ (and telescoping) matters, not integrality.

False. That causes thrashing (see figure s01): sitting exactly at $n=s/2$ and alternating push/pop retriggers an $O(n)$ resize every operation, breaking $O(1)$ amortized — you must shrink at a lower threshold (shrink when $n<s/4$) to leave slack.

The expensive copy happens only once every $n$ pushes (see the resizing schedule, figure s01); those geometrically-spaced copies sum to $<2m$ total (a Geometric Series), giving $O(1)$ amortized — see Dynamic Arrays / Table Doubling.

Sign flip. It is ${\hat{c}}_i=c_i+\Phi (D_i)-\Phi (D_{i-1})$ — actual cost plus the change in potential, so cheap ops that raise $\Phi$ get charged more.

Both wrong. The telescope leaves $\Phi (D_m)-\Phi (D_0)$ (final minus initial), and validity needs $\Phi (D_m)\ge \Phi (D_0)$ so that $\sum {\hat{c}}_i\ge \sum c_i$.

Undercharge. A single $0\to 1$ set needs $1 to act and $1 saved on that bit to later pay its own $1\to 0$ carry-flip, so you must charge $2 (walked step-by-step in the box below).

Missing the $\Delta \Phi$. Push raises $n$ by 1 so $\Phi$ rises by 2; $\hat{c}=1+2=3$. That extra 2 is exactly the savings that later pays the copy.

The sequence of $m$ operations runs in $O(m)$, not $O(1)$; amortized cost is per operation, and there are $m$ of them.

The formula $\Phi =2n-s$ is only used in the load regime $n\ge s/2$; below it we switch to the explicit piecewise form $\Phi =\frac{s}{2}-n$ (valid for $n<s/2$). Both pieces are $\ge 0$, agree at the join $n=s/2$ (both give $0$), and each is engineered to rise toward its own resize so it can pay for that resize.

So that when we sum over all operations the middle terms cancel (telescope), leaving only $\Phi (D_m)-\Phi (D_0)$; the $+$ sign is what makes cheap ops "prepay" by banking potential.

They bank energy so that a later rare expensive op can drop $\Phi$ sharply and cancel its large actual cost, keeping every $\hat{c}$ small — see the Fibonacci Heaps and Splay Trees analyses which rely on exactly this.

Because it needs no assumption about inputs; it holds against an adversary who picks the worst possible sequence, giving a guarantee not an expectation.

If resizes happened every constant number of pushes instead of doubling, the copy costs would sum to $\Theta (m\cdot n)$; doubling makes the cost of the $r$-th resize $2^r$ but spaces them so the sum is a Geometric Series $<2m$.

After a shrink or grow you always land at $n$ near $s/2$, so the array is half full either way. To force the next resize you must change $n$ by about $s/4$ (either fill up to $s$, or drain down to $s/4$). That means at least $\Theta (s)$ cheap operations must happen between any two $O(s)$ resizes — their banked potential prepays the resize, giving $O(1)$ amortized. Any threshold with a constant gap works; $1/4$ is the simplest.

A single find can be $O(\log n)$ or worse, but each such traversal flattens the tree, cheapening all future finds — the cost is only reasonable when averaged over the sequence (giving near-$O(\alpha (n))$).

Different $\Phi$ distribute the same total work differently across operations; the sum $\sum {\hat{c}}_i$ still upper-bounds the fixed $T(m)$, so the total guarantee is identical.

To make the invariant checkable: each element carries the exact credit needed to pay for its own future expensive event (its move or its bit-flip), so you can prove locally that the payment is always available.

Just $\hat{c}$ for one op ($\le 3$); with one operation the "average over a sequence" is simply that one operation's charge, and no resize savings are needed yet.

$T(0)=0$ and $T(m)/m$ is undefined at $m=0$; the amortized claim is vacuous — there is no operation to charge.

Not strictly; you only need $\Phi (D_m)\ge \Phi (D_0)$. But a nonzero $\Phi (D_0)$ adds a one-time $-\Phi (D_0)$ slack to the bound, so setting it to 0 keeps the accounting clean.

Yes; each such increment does exactly one $0\to 1$ set, costs $1 real and $2 charged, so it is even below budget. The $O(1)$ bound holds for any sequence, easy or pathological.

$\Theta (m)$, not $O(1)$: resizes now occur every 10 pushes and the $r$-th copies $\approx 10r$ elements, an arithmetic series summing to $\Theta (m^2/10)$, so per-push cost is $\Theta (m)$ — geometric growth is essential.

${\hat{c}}_i=c_i$; amortized equals actual, so you gain nothing — it is a valid but useless choice that just re-derives worst-case per op.