Amortized O(1) operations: Question bank — Coding deep dive

Reminders of the vocabulary these questions lean on:

Amortized cost = total cost of $n$ operations $\div n$ — a worst-case guarantee across a sequence.
Load factor $α = \frac{size}{capacity}$ — see Load Factor.
Geometric vs arithmetic growth — doubling vs adding a constant, see Geometric Series.

True or false — justify

Amortized O(1) means every single operation runs in O(1) time.

False. A single resize genuinely copies all

n

elements, so it is

O (n)

; amortized only bounds the total over a sequence, letting rare spikes hide behind many cheap ops.

Amortized analysis is the same thing as average-case analysis.

False. Average-case averages over a probability distribution of inputs; amortized is a deterministic worst-case over a sequence — no randomness, holds for every input order.

Doubling gives amortized O(1), but tripling (growth factor 3) does not.

False. Any factor

> 1

works — the copies still form a geometric series that sums to a constant multiple of

n

; only the constant changes, not the

O (1)

class.

Growing the array by a fixed

+ 100

each time is fine because 100 is large.

False. Fixed additive growth means

\approx n /100

resizes each copying up to

n

elements →

O (n^{2})

total →

O (n)

amortized. You need multiplicative growth; the constant 100 doesn't change the order.

The potential function

Φ = 2 \cdot size - capacity

can go negative during normal operation.

False if the array stays at least half full (right after a resize

Φ = 2

). It's designed to be

\geq 0

so amortized cost never undercounts; a valid potential must never dip below its starting value.

If a data structure has amortized O(1) inserts, it is safe for a real-time flight-control loop.

False. One resize is an

O (n)

latency spike; a hard-real-time deadline can be missed on that single call even though the long-run average is constant.

The "3" in the accounting method is a fundamental constant of doubling.

False (it's factor-dependent). Doubling happens to give

\leq 3

; a different growth factor gives a different constant charge. The constancy is fundamental, the exact number is not.

Rehashing a hash table and resizing a dynamic array are analysed by the same argument.

True. Rehash = allocate a doubled table + re-place every element, exactly resize-plus-copy; the geometric-series bound

< 2 n

applies identically (assuming O(1) per probe).

Spot the error

"Copy cost for

n

doubling-pushes is

1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}

, so inserts are amortized O(n)."

The error is using an arithmetic series. Doubling copies at sizes

1, 2, 4, \dots

(a geometric series summing to

< 2 n

), not every integer. The arithmetic sum is the +1-growth case, not doubling.

"Amortized cost

= \frac{most expensive operation}{n}

Wrong numerator. Amortized cost is total cost of all

n

operations divided by

n

, not just the single worst one — you must sum every cheap write too.

"In the potential method, amortized cost

=

actual cost

- ΔΦ

Sign error. The correct formula is amortized

=

actual

+ ΔΦ

. During a resize

ΔΦ

is a large negative number, and adding it cancels the big actual copy cost.

"Since resizing is

O (n)

and we do

lo g_{2} n

resizes, total copy work is

O (n lo g n)

Wrong: the resizes don't each cost

n

. They cost

1, 2, 4, \dots, 2^{m}

, which sum to

< 2 n

— the sizes grow, so the sum is dominated by the last term, giving

O (n)

, not

O (n lo g n)

"Amortized O(1) needs random input to work, like average-case."

No randomness is involved. Doubling guarantees

\leq 3

per push for any order of insertions; it is a worst-case-over-sequence bound.

"Because one push can cost

O (n)

, the sequence of

n

pushes costs

O (n^{2})

The expensive pushes are rare and their costs form a geometric series. Summing actual costs gives

\leq 3 n = O (n)

total, not

O (n^{2})

Why questions

Why does doubling (not adding) keep the total copy cost linear?

Because copy costs

1 + 2 + 4 + \dots + 2^{m} = 2^{m + 1} - 1 < 2 n

— a geometric series is dominated by its last term, so the whole history costs only a constant multiple of the final size.

Why do we charge each push 3 units in the accounting method instead of 1?

The extra 2 are saved as credit on the new element so that when a future doubling copies it (and helps pay for an older neighbour), the bank never goes negative — pre-paying the rare expensive copies.

Why must the potential drop sharply exactly at a resize?

The stored-up potential (built by cheap pushes each adding

+ 2

) is precisely the "saved work" that gets spent to cancel the big

O (n)

copy, keeping the amortized cost flat at 3.

Why is amortized O(1) a stronger claim than "usually fast"?

It's a guaranteed upper bound on the total cost regardless of input, so it holds even for an adversarially chosen sequence — "usually" would allow a bad case to blow up.

Why does a lower load-factor threshold (say resize at

α = 0.5

0.9

) not change the O(1) amortized class?

A lower threshold just changes the constant (more spare room means more frequent but still geometrically-spaced resizes); the geometric-series argument and hence

O (1)

order are unchanged.

Why can't we amortize away the latency of a single resize, only its cost?

Amortization redistributes cost on paper across the sequence, but in real time the copy still executes all at once — the wall-clock spike is physically there even though its accounting is spread out.

Edge cases

What is the amortized cost when you push exactly one element into an empty array?

For a single push there's nothing to average over — the bound "

\leq 3

" is asymptotic; one operation can legitimately cost 1 (write, no resize) or more if a resize triggers. The guarantee is about long sequences.

Does the

< 2 n

copy bound still hold if

n

lands exactly on a power of two (e.g. push the

8

th item into a cap-8 array)?

Yes. The last resize copies

\leq n

elements, and

2^{m + 1} - 1 < 2 n

holds whether or not

n

is a power of two — the bound is designed to cover the worst alignment.

If you interleave pushes with pops that never trigger a shrink, is insert still amortized O(1)?

Yes — pops that don't resize are

O (1)

and don't disturb the doubling schedule; the geometric copy bound over the pushes is untouched.

If the array shrinks by halving the instant it drops below half full, can amortized cost break?

Yes — a push-pop-push-pop sequence at the boundary could force resize on every op ("thrashing"), giving

O (n)

per op. The fix is hysteresis: shrink only below

\frac{1}{4}

full, so growing and shrinking thresholds don't overlap.

What happens to amortized insert cost as the growth factor approaches 1 from above (e.g.

1.001 \times

It stays

O (1)

in order but the constant blows up like

\frac{1}{factor - 1}

— near-1 factors resize almost every push, so amortized cost is huge though technically still constant.

What is the amortized cost of a resize-triggering push in isolation, ignoring the sequence?

Its actual cost is

O (m)

(copy

m

+ write 1). Only when combined with the potential drop, or averaged over the preceding cheap pushes, does it become 3 — never call a lone resize "O(1)".

Connections

Amortized O(1) operations — the parent note these traps drill.
Dynamic Arrays — where doubling and thrashing live.
Hash Tables · Load Factor — rehash-threshold edge cases above.
Geometric Series — the "spot the error" arithmetic-vs-geometric confusions.
Potential Method — the sign and drop-at-resize questions.
Stack with Multipop — another amortized structure to test the same reasoning.
Big-O Notation — order-vs-constant distinctions throughout.