Motivation
An insertion into an array is usually cheap, but occasionally the array is full and every existing element must be copied to a larger allocation. A worst-case bound for one insertion can therefore be linear in the current number of elements. Charging that worst case to every insertion greatly overstates the cost of a long sequence: expensive copies are separated by many cheap operations.
Amortized analysis bounds the total cost of a sequence and divides that bound among its operations. It is a worst-case statement about the entire sequence, not an average over random inputs. We analyze a precise insertion-only dynamic array and give two proofs of the same linear total bound.
Definitions
Initially the array is empty with capacity . A doubling insertion works as follows.
Definition 1.12.1
(Doubling insertion array)
To insert an element when the current size is and the capacity is : if , write the new element in the next free slot. If , allocate capacity , copy all existing elements, and then write the new element. The cost is one unit per copied element and one unit for the new write. Allocating storage itself and releasing old storage are treated as zero cost in this model; another model must include their costs separately. For a sequence of insertions, the actual cost is the sum of these units.
Definition 1.12.2
(Potential of an array state)
The potential of a state with size and capacity is
The amortized cost of one operation is its actual cost plus the change in potential. Potential is an accounting quantity, not stored computational work; its usefulness is that changes telescope over the sequence.
Theorems
Theorem 1.12.3
(Linear total cost)
For every integer , the total cost of insertions under the doubling rule is at most . Thus the amortized cost is at most three units per insertion, although a single insertion can cost .
Theorem 1.12.4
(Capacity bound)
After any positive number of insertions, the capacity satisfies . At the initial empty state the capacity is one.
Proof sketch or proof idea
Proof
(Potential proof of the linear bound)
Initially , and the potential is always nonnegative. If an insertion does not resize, its actual cost is one. Increasing by one changes by at most two, so its amortized cost is at most three.
If the array is full, before insertion and the actual cost is . The old potential is . After doubling and writing, and , so the new potential is . The amortized cost is therefore . Summing over all operations telescopes: total actual cost plus final potential minus initial potential is at most . Since the final potential is nonnegative and the initial potential is zero, total actual cost is at most .
Proof X-ray
Why this potential pays for the copy
The proof has one design choice and three checks. The choice is : it is zero at the start, it rises by at most two per cheap insertion, and it equals exactly when the array is full, the same as the copying cost. At a resize that stored amount is released, so the amortized cost is rather than . The three checks are the cheap case (, so charge at most three), the resize case (which uses and ), and the closing step, where and turn the telescoped identity into the inequality .
The same dissection shows what a different growth rule would break. If a full array grew from to instead, the potential after the insertion would be , so and the amortized cost would be . Nothing is released at the resize, so the potential cannot pay for the copy; the geometric choice is what makes the potential fall.
Proof
(The capacity invariant)
Size never exceeds capacity. Before the first resize, the only positive size is one with capacity one. After a resize from to , the new size is , so the new capacity is strictly less than twice the new size. Subsequent non-resizing insertions only increase size, preserving the strict inequality. Induction over operations proves the result.
Proof
(Aggregate proof of the same bound)
The copies at successive resizes have costs , ending with a capacity strictly smaller than the final positive size . Their sum is less than ; the new writes add . This also gives a total below for . The geometric series counts each resize once rather than charging its cost to every operation.
Concept lensAlgebraic
The exact total as a closed form
Resizes occur at insertions and copy elements, for every with . The copies therefore sum to , and the exact total for is
For this is . Since , the total is below , as the theorem states.
Worked examples
Worked example 1.12.5
(The first four insertions)
The first insertion costs one and leaves size/capacity . The second copies one and writes one, costs two, and leaves . The third copies two and writes one, costs three, and leaves . The fourth writes one without resizing and leaves . Total actual cost is .
Worked example 1.12.6
(A costly single operation)
After eight insertions the capacity is eight. The ninth insertion copies eight existing elements and writes one, so its actual cost is nine. This does not contradict the theorem: the theorem bounds all nine insertions together, not each individual actual cost by three.
Worked example 1.12.7
(A potential calculation)
Immediately before resizing a full capacity-four array, and . After insertion it is with . Actual cost is five, while amortized cost is . The negative potential change offsets part of this one operation's actual cost.
Common mistakes
Counterexample mode
Growing by a fixed amount is not enough
A plausible claim is that any rule that copies everything when the array is full gives a linear total. Take the rule that, when full, increases the capacity by exactly one. The second insertion copies one element, the third copies two, and the th copies . For the copies cost and the ten writes add , for a total of , already above . In general the copying alone costs , so the total is quadratic. The claim fails because the resize spacing is not geometric. The repair is the hypothesis that the capacity is multiplied by a fixed factor , as in doubling.
Common mistake
(Amortized is not expected)
The doubling rule makes no random choices. Its linear sequence bound holds for every insertion sequence under the cost model. Calling the bound an average-case result would require a probability distribution that is not part of the theorem.
Common mistake
(Constant amortized cost is not constant latency)
The guarantee does not imply that every insertion is constant time: the ninth insertion above costs nine, and the insertion after elements costs . It also does not cover deletions, shrinking, or the cost of allocating and initializing every new slot unless those operations are included in a new analysis.
Following the potential over a sequence
Write for the actual cost and for the potential after insertion , with . The amortized cost is . Adding the first equalities gives
Every intermediate potential cancels. Since each and , the actual total is at most . The proof does not require the potential to increase at every step: on a resize it typically falls. It requires the telescoping identity and a lower bound on the final potential.
For the first four insertions, the potentials after each operation are . The changes are , so the amortized costs are . Their sum is , equal to actual total plus final potential . The final stored potential is not an extra actual charge; it is the difference between the upper-bound accounting and the work already performed.
Credits as an alternative accounting proof
One can also charge each insertion three credits: one pays for its own write and two are saved. When capacity grows from to , copying costs credits. After a previous resize to capacity , at least insertions have occurred before that capacity becomes full again, including the insertion that triggered the previous resize. Their two saved credits each provide at least credits. The first resize from capacity one is covered by the two credits saved by the first insertion. Saving any unused credits preserves a nonnegative balance.
This credit interpretation is a proof only after specifying where the credits come from and verifying the balance at every resize. Saying that a cheap operation "pays for later" is an intuition; the count of intervening insertions makes it precise. The potential proof encodes the same broad idea algebraically, although the numerical potential need not equal the balance of this particular credit scheme at every state.
Changing the growth factor
Doubling is one example of geometric growth. Suppose the initial capacity is one and every full array is replaced by capacity , where is a fixed integer, while copying and write costs are unchanged. The copied capacities are . If the last copied capacity is , it is strictly less than the final positive size . Hence their sum is at most
Adding the writes gives total cost below . This bound is valid for the specified fixed integer growth factor; rounding rules for a noninteger factor require their own invariant.
Geometric growth trades time for unused capacity. Immediately after a resize from to , the size is , so capacity is less than times the size. Between resizes the size grows and the capacity stays fixed. Thus after any positive number of insertions . Larger changes both the copying bound and the storage bound; the best engineering choice may depend on allocation costs, memory limits and workload, which are not part of this mathematical model.
Potential choices and validity
A potential function is not unique. The chosen is convenient because it is nonnegative even in the initial empty state. A different function may prove the same total bound with different constants. What matters is that the amortized-cost inequalities hold for every allowed operation, that the initial value is known, and that the final value has a suitable lower bound.
Common mistake
(Assuming the potential must be nonnegative)
The expression without the maximum equals in the initial state , so it is not nonnegative. What the telescoped identity actually needs is , not . For this still holds, because after any positive number of insertions (capacity bound), so . Dropping a negative or unchecked final potential without such a check is an invalid step; the maximum avoids that bookkeeping in the stated insertion-only model.
Amortized bounds are robust to the values inserted: no assumption about their distribution appears in either proof. They are nevertheless model-specific. If each copy is more expensive than a constant, or allocation initializes every slot, include those costs. For example, charging a constant number of units per newly allocated slot still yields a geometric sum and linear total work, but the constant three no longer follows unchanged. If copying an element itself has variable cost, the unit-cost theorem must not be applied without accounting for that variability.
Why shrinking needs a separate rule
This unit never removes elements. If deletion and shrinking are added, a capacity policy can thrash: expanding at full capacity and shrinking immediately when occupancy drops just below one half can cause alternating insertions and deletions to trigger repeated copies of a large array. A common remedy is to leave a gap between growth and shrink thresholds, but its correctness and amortized bound require a potential tailored to both operations. The insertion-only potential and proof above do not establish that result.
Space and time guarantees also describe different resources. The capacity inequality bounds reserved slots after each insertion; the amortized proof bounds total counted writes and copies. A resize may temporarily require both old and new allocations, so peak memory during that operation depends on the allocation model. Neither the final-capacity bound nor the unit-cost time proof alone specifies that peak.
Summary
A doubling array occasionally copies all stored elements, but copies occur at exponentially increasing capacities. Both a geometric aggregate sum and a nonnegative potential show linear total cost for insertions. Amortized constant cost is compatible with occasional expensive individual operations.
Exercises
Quick check
(What are the actual cost and new capacity of the fifth insertion?)
Compare the size and capacity before the insertion.
Solution · Answer
Before it, size and capacity are four. The insertion copies four and writes one, costing five; the new capacity is eight.
Quick check
(What is immediately before and after inserting into a full capacity-two array?)
Apply to the state before and after the doubling.
Solution · Answer
Before, . After doubling and insertion, .
Quick check
(Why does the aggregate copy-cost series have geometrically increasing terms?)
Look at how the capacity changes at each resize.
Solution · Answer
Every resize doubles capacity, so the numbers of copied elements are successive powers of two.
Quick check
(Does the theorem prove constant worst-case latency for an individual insertion?)
Recall the ninth insertion in the worked examples.
Solution · Answer
No. A resizing insertion copies all current elements and can have linear actual cost. The theorem bounds the total over a sequence.