Sums and series · heyrian.dev

01 / Read the resize trace

A rare pause may be part of a cheap sequence.

Suppose an array starts with room for 8 elements. When it fills, the implementation allocates a buffer twice as large and copies the old elements into it. This repeats as needed. We will model only the element-copy work, assume allocation succeeds, and treat copying one element as one unit of work. Those are useful assumptions for counting, not a complete runtime benchmark.

To append 41 elements, the capacity sequence is 8 → 16 → 32 → 64. Growth happens before the 9th, 17th, and 33rd elements are written. The resize copies 8, then 16, then 32 existing elements. Appending the 41st element does not resize again because 64 slots are already available.

Case file / In-memory batch Count copying across the complete append sequence.

Starting capacity: 8 element slots.
Growth policy: Double capacity whenever the buffer is full.
Work counted: Existing elements copied during each resize.
Question: How many element copies happen while appending 41 elements?

In practice · A latency review for a batch importer Total copy work and amortized cost

“The 33rd append copied 32 values. Does that mean every append costs 32 copies?”

— An engineer reviewing a short latency spike

A technically grounded answerNo. That append crossed a capacity boundary, so it copied 32 existing values once. Across 41 appends, the modeled resize copies are 8 + 16 + 32 = 56 elements. Counting one write for each new value gives 41 + 56 = 97 element writes total, or about 2.37 writes per append on average. The average describes this whole sequence; the boundary append still has a higher individual cost.

Where the term helpsUse a finite sum when the decision concerns cumulative work over a known or bounded sequence. For tail latency, also inspect the individual resize events: a small average does not erase a pause on one operation.

02 / Add the copied elements

Doubling makes the resize costs a geometric series.

A series is a sum of terms. In a geometric series, each term is the previous term multiplied by the same ratio. For a starting capacity C₀ and a doubling policy, if m resizes occur, the copied capacities are C₀, 2C₀, 4C₀, …, C₀·2^m−1.

For first term a, common ratio r ≠ 1, and m terms, the finite sum is Sₘ = a(1 − r^m) / (1 − r); when r = 1, it is simply m × a. For doubling, r = 2, so the capacity-copy sum simplifies to Sₘ = C₀(2^m − 1). Here m is the number of resize events, not the number of appends. There are three resizes, so the substituted calculation is shown below.

Finite geometric sumSₘ = a(1 − r^m) / (1 − r)

Substitute capacity and resize count8 elements × (2³ − 1)

Evaluate the dimensionless factor8 elements × 7 = 56 elements copied

The factor 2³ − 1 = 7 has no unit; multiplying it by a capacity measured in elements leaves the answer in elements. You can sanity-check by listing the terms: 8 + 16 + 32 = 56. A formula is useful partly because it agrees with the trace.

The same finite addition can answer a timing question. If a client waits 1, 2, 4, and 8 seconds before four later attempts, those scheduled pauses total 1 + 2 + 4 + 8 = 15 seconds under this illustrative schedule. That is timer-only wait; request durations are excluded. A maximum-delay cap or jitter changes the terms, so sum the schedule the client actually uses. Retry safety and load are separate questions covered in the retry lesson.

03 / Separate total from average

One total can describe the sequence without describing every step.

The 56 copies are cumulative extra work. The 41 new values are also written once, so this simple model counts 41 + 56 = 97 element writes. Averaged over 41 appends, that is 97 ÷ 41 ≈ 2.37 element writes per append. The value is an average for this particular finite prefix, rounded to two decimal places; it is not a guarantee of 2.37 writes for each operation.

For any number N > 8 of appends under this exact doubling policy, the copied capacities form a prefix of 8 + 16 + …. Their sum is less than the final capacity, and that final capacity is less than 2N. So this model has fewer than 2N resize copies and fewer than 3N total element writes, including the N new values. This is why the sequence has constant amortized copy-plus-insert work per append even though a resize append can copy many elements.

Amortized means spreading total cost across a sequence according to a stated accounting model. It is not a probability, and it does not say a slow event cannot happen. A service with a strict per-request latency target may still need preallocation, incremental migration, or another data structure.

04 / Change the number of appends

Watch the next resize boundary add a whole term.

Change the batch size from 0 to 5,000. The model starts with eight slots and doubles whenever the next append finds the buffer full. Notice how the copy total stays fixed between boundary crossings, then jumps by the old capacity at the next resize.

Series lab / Doubling array Count element copies and writes for one finite batch.

Elements to append (0–5,000)

Resize copy terms (elements): 8 + 16 + 32

Total resize copies: 56 elements

Closed-form cross-check: 8 × (2³ − 1) = 56 elements

New-element writes: 41 elements

Total modeled writes: 97 element writes

Average over this batch: 2.37 element writes per append

05 / Practice in code

Count both the resize terms and the inserts.

The examples accept at most 5,000 appends, record each capacity copied, and compare the iterated sum with the closed form. At this bound the counts are small exact integers in both implementations. Try 8 and 9 to see the first boundary, then 40 and 41 to see why the average can fall after a resize even while cumulative work increases.

Compare the same finite sequence in TypeScript and Go.

Both programs count the same resize copies, new writes, and geometric formula.

Read in

Compare with

Compare languages

TypeScriptFinite geometric sum for array growth work

array-growth.ts

export type GrowthWork = {
	appends: number;
	resizedCapacities: number[];
	resizeCopies: number;
	formulaCopies: number;
	totalWrites: number;
	averageWritesPerAppend: number | null;
};

/** Count element-copy work for a doubling array, with small explicit safe bounds. */
export function countGrowthWork(appends: number, initialCapacity = 8): GrowthWork {
	if (!Number.isSafeInteger(appends) || appends < 0 || appends > 5_000) {
		throw new RangeError('Appends must be a whole number from 0 through 5,000.');
	}
	if (!Number.isSafeInteger(initialCapacity) || initialCapacity < 1 || initialCapacity > 8_192) {
		throw new RangeError('Initial capacity must be a whole number from 1 through 8,192.');
	}

	let capacity = initialCapacity;
	const resizedCapacities: number[] = [];
	for (let index = 0; index < appends; index += 1) {
		if (index === capacity) {
			resizedCapacities.push(capacity);
			capacity *= 2;
		}
	}

	const resizeCopies = resizedCapacities.reduce((sum, oldCapacity) => sum + oldCapacity, 0);
	const formulaCopies = initialCapacity * (2 ** resizedCapacities.length - 1);
	if (!Number.isSafeInteger(resizeCopies) || resizeCopies !== formulaCopies) {
		throw new RangeError(
			'The copy count exceeded the exact integer range or failed its formula check.'
		);
	}
	const totalWrites = appends + resizeCopies;
	return {
		appends,
		resizedCapacities,
		resizeCopies,
		formulaCopies,
		totalWrites,
		averageWritesPerAppend: appends === 0 ? null : totalWrites / appends
	};
}

console.log(countGrowthWork(41));

GoFinite geometric sum for array growth work

array-growth.go

package main

import (
	"errors"
	"fmt"
)

type GrowthWork struct {
	Appends                int
	ResizedCapacities      []int
	ResizeCopies           int
	FormulaCopies          int
	TotalWrites            int
	AverageWritesPerAppend *float64
}

// Count element-copy work for a doubling array, with small explicit bounds.
func countGrowthWork(appends, initialCapacity int) (GrowthWork, error) {
	if appends < 0 || appends > 5_000 {
		return GrowthWork{}, errors.New("appends must be a whole number from 0 through 5,000")
	}
	if initialCapacity < 1 || initialCapacity > 8_192 {
		return GrowthWork{}, errors.New("initial capacity must be from 1 through 8,192")
	}

	capacity := initialCapacity
	resizedCapacities := make([]int, 0)
	for index := 0; index < appends; index++ {
		if index == capacity {
			resizedCapacities = append(resizedCapacities, capacity)
			capacity *= 2
		}
	}

	resizeCopies := 0
	for _, oldCapacity := range resizedCapacities {
		resizeCopies += oldCapacity
	}
	formulaCopies := initialCapacity * ((1 << len(resizedCapacities)) - 1)
	if resizeCopies != formulaCopies {
		return GrowthWork{}, errors.New("iterated copy count did not match the geometric sum")
	}
	totalWrites := appends + resizeCopies
	var average *float64
	if appends > 0 {
		value := float64(totalWrites) / float64(appends)
		average = &value
	}
	return GrowthWork{
		Appends: appends, ResizedCapacities: resizedCapacities,
		ResizeCopies: resizeCopies, FormulaCopies: formulaCopies,
		TotalWrites: totalWrites, AverageWritesPerAppend: average,
	}, nil
}

func main() {
	work, err := countGrowthWork(41, 8)
	if err != nil {
		panic(err)
	}
	fmt.Printf("copied capacities %v; resize copies %d; formula copies %d; total writes %d; average %.2f writes/append\n",
		work.ResizedCapacities, work.ResizeCopies, work.FormulaCopies, work.TotalWrites, *work.AverageWritesPerAppend)
}

06 / Challenge the assumptions

Ask what changes when the capacity policy changes.

Suppose the batch has 70 elements and starts with capacity 16. Under doubling, resize copies are 16 + 32 + 64 = 112 elements. Including the 70 new values, the model counts 182 element writes. The geometric formula gives 16 × (2³ − 1) = 112 copies. This is a new input, so do not carry over the 8-slot result.

Now change the design: if the batch size is known and the system reserves 70 slots before appending, this model has 70 writes and no growth copies. The reservation trades spare memory and up-front allocation for fewer resize events. If inputs arrive incrementally or may be much larger than expected, the reservation itself needs a justified bound.

Transfer / Batch import Choose the measure that matches the risk.

Boundary check: At 8 appends: no resize. At 9: copy 8 existing elements.
Exact later edge: At 40: capacities 8, 16, and 32 have been copied; the array has 56 copy work units.
Next append: At 41, capacity is still 64, so no additional resize copy occurs.
Decision: For throughput, estimate aggregate operations; for latency, inspect boundary operations and allocation behavior.

In practice · A batch-size change request Finite model and transfer

“Can we use the 41-item estimate for every import?”

— A developer reviewing an incoming batch limit

A technically grounded answerOnly if the capacity start, growth rule, and maximum batch size remain the same. For 70 items with capacity 16, the doubled capacities copied are 16, 32, and 64: 112 copies. If the runtime uses another growth rule or the batch reserves capacity first, this count changes. First inspect actual capacities or document the container policy, then measure allocation and latency on representative sizes.

Where the term helpsA finite series supports a decision only within its stated bounds. Recalculate when the term count or ratio changes, and validate implementation behavior when the model is meant to predict a real runtime.

Take the idea with you: list the repeated costs, identify the common ratio, count the terms that actually occur, and keep the total separate from the cost of one operation.