Arrays and amortised cost

Every cost claim so far assumed that reading a[i] costs one step, and whether that is true depends entirely on how the elements are laid out in memory.

One block, and what an index really is

An array is a single contiguous block of memory holding $n$ elements of equal size $s$ bytes, starting at some base address $B$ . That is the whole definition, and every property of arrays follows from it mechanically.

The element at index $i$ begins at address $B + i s$ . That is one multiplication and one addition, whatever $i$ is. Reading a[0] and reading a[999999] cost the same, because neither involves looking at anything in between. This is what random access means, and it is not a small thing: it is the property that makes binary search possible three lessons from now, and the property a linked list gives up in the next lesson.

The cost is the same, but the time need not be, and the difference is worth naming once. Under the RAM model both reads are one step. On real hardware a read whose target is already in the level-1 cache takes about a nanosecond, and one that goes out to main memory takes on the order of a hundred. Because caches load whole lines, typically 64 bytes, walking an array from front to back gets seven or eight elements free for every one that costs a trip to memory. Arrays are fast in practice for a reason the RAM model cannot see, and every structure in this course that scatters its elements pays a price the step count does not show.

Example. An array of 8-byte numbers begins at address 4096. At what address does element 250 begin, and how many memory cells were examined to work that out?

The address is $B + i s = 4096 + 250 \times 8 = 6096$ . No cells were examined. The address came from arithmetic on $i$ alone, which is precisely why the cost does not depend on $i$ .

Now you. The same array is reindexed so that its first valid index is 1 rather than 0, with the block still starting at 4096 and element 1 stored first. Where does element 250 begin?

Answer

The formula becomes $B + (i - 1) s = 4096 + 249 \times 8 = 6088$ . One extra subtraction, still constant cost, which is why the choice between 0-based and 1-based indexing is a matter of convention rather than performance.

The price of contiguity

The same property that makes indexing free makes structural change expensive, and the two are the same fact seen from opposite sides. Contiguity says element $i$ is at $B + i s$ ; that formula has to keep holding after the change, so the elements must physically move.

To insert a value at position $k$ in an array of $n$ elements, every element from $k$ to $n - 1$ must move one slot to the right, which is $n - k$ moves. Inserting at the front costs $n$ moves; at the back it costs none. If insertion positions are uniformly distributed over the $n + 1$ possible slots, the expected number of moves is about $n / 2$ . Deletion is the same in reverse: removing element $k$ shifts $n - k - 1$ elements left.

So an array's cost table has two very different entries. Read or write by index: $Θ (1)$ . Insert or delete anywhere but the end: $Θ (n)$ .

There is one escape worth knowing, because it is used constantly and looks like cheating. If the order of the elements does not matter, deleting element $k$ can be done by moving the last element into slot $k$ and shrinking the length, which is $Θ (1)$ . Order is a requirement people assume without noticing they have assumed it, and dropping it here turns a linear operation into a constant one.

An array that grows

A block of memory has a fixed size, decided when it is allocated. Yet every language offers something that behaves like an array you can push onto forever: JavaScript's Array, C++'s std::vector, Java's ArrayList, Python's list. All of them are the same construction, called a dynamic array or growable array, and the construction is worth deriving because its analysis needs a genuinely new idea.

The structure holds three things: a block, its capacity (how many elements the block can hold) and its length (how many it currently holds), with length never exceeding capacity. Pushing writes to slot length and increments the length, which is $Θ (1)$ , until length equals capacity. At that point the push cannot proceed, so the structure allocates a bigger block, copies every existing element across, frees the old block, and then does the write.

That copy is $Θ (n)$ . So a single push has worst-case cost $Θ (n)$ , and if you stop the analysis there you conclude that dynamic arrays are terrible, which contradicts the fact that everyone uses them. The worst case is a true statement about one operation and a misleading statement about a sequence of them, because an expensive push guarantees that the next many pushes are cheap.

Amortised cost

Amortised analysis asks a different question: not what the worst single operation costs, but what the worst sequence of $m$ operations costs, divided by $m$ . It is a worst-case statement, not an average-case one. There is no probability in it and no assumption about which inputs occur. It says: however you choose the operations, the total is bounded.

Take the growth rule "when full, allocate a block of double the capacity". Start from capacity 1 and push $n$ elements. Reallocation happens when the length reaches 1, 2, 4, 8, and so on, and the copy at each of those points moves the current contents: 1 element, then 2, then 4, and so on. The total number of elements copied over the whole sequence is

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

where $2^{k}$ is the final capacity. Concretely, growing to a million elements from capacity 1 does 20 reallocations and copies 1,048,575 elements in total, roughly one copy per element pushed.

Add the $n$ writes of the pushed values themselves and the total for $n$ pushes is under $3 n$ operations, so the amortised cost of a push is $O (1)$ : about two operations each, a write and a copy. No individual push is guaranteed cheap. The sequence is.

Now try the other obvious growth rule: when full, allocate a block with a fixed number of extra slots, say 1000 more. Reallocation now happens every 1000 pushes, and the copies are 1000, then 2000, then 3000, and so on. Reaching a million elements takes 999 reallocations and copies

1000 + 2000 + \dots + 999000 = 1000 \cdot \frac{999 \cdot 1000}{2} = 499 {,} 500 {,} 000

elements: 476 times more copying than doubling, for the same result. In general, growing by a fixed $c$ costs $Θ (n^{2} / c)$ total, so the amortised cost per push is $Θ (n / c)$ , which is linear, not constant. The constant $c$ postpones the problem and does not remove it. This is the whole argument for multiplicative growth, and it is why every library implementation uses a growth factor rather than a growth increment.

Example. A dynamic array with growth factor 2 starts at capacity 1 and receives 1000 pushes. How many reallocations occur, and how many element copies in total?

Capacities go 1, 2, 4, ..., 1024, so reallocations happen at lengths 1, 2, 4, ..., 512: ten of them. The copies total $1 + 2 + 4 + \dots + 512 = 1023$ elements. Against 1000 pushes that is 1.02 copies per push, and adding the pushes themselves gives about 2.0 operations per push, exactly as the amortised bound predicts.

Now you. The same array instead grows by 100 slots each time it fills, starting from capacity 100. How many copies in total to reach 1000 elements, and how does that compare?

Answer

Reallocations happen at lengths 100, 200, ..., 900, which is nine of them, copying 100, 200, ..., 900 elements: $100 (1 + 2 + \dots + 9) = 100 \times 45 = 4500$ copies. That is 4.4 times the doubling scheme's 1023, at $n = 1000$ . The gap widens with $n$ , since one grows linearly and the other quadratically.

Which factor, and what it costs in memory

Doubling is not the only multiplicative rule, and the choice is a real engineering trade rather than a detail.

With growth factor $g$ , the capacities form a geometric sequence and the total copies to reach $n$ elements are about $n / (g - 1)$ . So $g = 2$ copies each element about once, $g = 1.5$ copies it about twice, and $g = 4$ about a third of a time. Larger $g$ means less copying.

The price is memory. Immediately after a growth the block is $g$ times larger than the data in it, so up to $(g - 1) / g$ of the allocation is empty: half the block wasted at $g = 2$ , three quarters at $g = 4$ . For an array of a hundred million records that is not a rounding error.

There is a subtler argument for $g = 1.5$ , and it is a nice example of a real constraint that no asymptotic analysis can see. Consider whether the memory freed by earlier reallocations can be reused for the next block. Under doubling, the total freed so far when asking for a block of size $2^{k}$ is $1 + 2 + \dots + 2^{k - 1} = 2^{k} - 1$ , which is always just short of what is needed, forever. Under any factor below the golden ratio $φ = 1.618$ , the freed blocks eventually add up to more than the next request, so an allocator can reuse them. Facebook's folly::fbvector uses 1.5 for exactly this reason, while std::vector in the GNU and LLVM standard libraries uses 2, and Python's list grows by roughly 1.125 with a small constant added, since it also cares about small lists.

Note also what shrinking must not do. If a dynamic array halves its block as soon as the length falls below half the capacity, then repeatedly pushing and popping across the boundary makes every operation reallocate, and the amortised bound collapses to $Θ (n)$ per operation. The standard fix is hysteresis: shrink only when the length falls below a quarter of the capacity, which leaves room for the length to move without triggering another reallocation.

Example. A dynamic array uses growth factor 1.5. Roughly how many element copies does building it up to $n = 10^{6}$ elements cost, and how much memory can be wasted at worst?

Total copies are about $n / (g - 1) = 10^{6} / 0.5 = 2 \times 10^{6}$ , so about two copies per element, twice the doubling scheme's one. The wasted fraction just after a growth is $(g - 1) / g = 0.5 / 1.5 = 1 / 3$ , so at worst about a third of the block is empty, against a half under doubling.

Now you. A dynamic array uses growth factor 4. How many copies per element does it make, and what fraction of the block can be empty?

Answer

Copies per element are about $1 / (g - 1) = 1 / 3$ , so a third of a copy each, three times less work than doubling. The wasted fraction just after a growth is $(g - 1) / g = 3 / 4$ , so up to three quarters of the allocation holds nothing. That is the trade in its starkest form: copying and memory move in opposite directions as $g$ changes.

What amortised does and does not promise

Amortised constant is a strong guarantee about totals and no guarantee at all about any individual operation, and the difference matters in exactly one setting, which is worth stating plainly rather than leaving as a footnote.

If a program is rendering a frame every 16 milliseconds, or holding a lock, or steering something, then a single push that stops to copy ten million elements is a failure even though the average is fine. Systems with that requirement use structures with worst-case constant bounds, which exist and are built by copying incrementally: on each push, move a few elements from the old block to the new one, so that the migration finishes before the new block fills. The total work is the same and the peak is bounded, at the cost of holding two blocks at once and of more complicated code.

For everything else, amortised constant is the right guarantee and dynamic arrays are the right default. The remaining problem is the one this lesson could not fix. Growing is solved, but inserting or deleting anywhere except the end is still $Θ (n)$ , and no growth policy touches that, because it is forced by contiguity itself. The elements are neighbours in memory, so making room for one means moving the rest.

The only way out is to stop requiring them to be neighbours. If each element carries the address of the next one, the elements can sit anywhere, and inserting between two of them is a matter of rewriting two addresses. That buys constant-time insertion and, as the next lesson shows, immediately loses the constant-time indexing this one opened with.