Time and space complexity.

01 / The idea

How much work is “a lot”?

A code review says a release check is “just a loop”. That sentence hides the input. Six release ids make six iterations harmless. Sixteen make a pairwise check 120 comparisons; 32 make 496. If the batch is a million items, the distinction is no longer editorial.

Complexity is a way to describe how work or storage changes as the input gets larger. It is a model of growth, not a promise about milliseconds. A fast machine, cache, compiler, network, and constant factors still decide the clock time for one workload.

The useful question is not “is this O(n)?” in isolation. It is “what does n count, what does one operation do, and what must stay in memory while it runs?” That is the question we will ask of one release batch three different ways.

02 / Name the rule

Count repeated work, then count growing memory.

Start with the input size. One loop whose body does constant work runs n times: O(n). Two loops nested over the same input can run n × n times: O(n²). Two loops one after the other still add to O(n), because n + n grows like n.

Then inspect what the operation creates or retains. A counter is O(1) extra space. A new array with one cell per input is O(n) extra space. Do not charge the input twice: the caller’s batch is retained in all three examples, but only the copy creates another n cells.

Big-O keeps the dominant growth and drops constant factors and smaller terms. That makes O(2n + 4) read as O(n), and n(n − 1) ÷ 2 read as O(n²). Keep the exact count when it helps a concrete decision; keep the bound when you need to compare larger inputs.

03 / Follow one operation

Watch the same input change shape.

The animation holds the input meaning steady and changes one decision at a time. First a pass visits four items. Then every pair of the same four meets. Doubling the input to eight takes the pairs from 6 to 28. An output copy keeps the linear work but adds linear storage, and a last chapter runs the pairs over sixteen items.

04 / Read the shape

One counter, two loops, or a second result?

Basic form is measure: it names the shape, validates n, and counts the visits, comparisons, or writes. The optional trace is for the lesson, not part of the cost claim. In the wild is reviewBatch, which runs the same shapes over the release ids themselves: check each id, compare every pair for a repeated release, or write one report line per id. The ids stay input; only the report counts as extra space.

The caller runs the same six ids three ways. Notice what the examples do not do: they do not measure wall-clock time or pretend that an array slot is a fixed number of bytes across languages. They make the growth rule inspectable instead.

export type Shape = 'scan' | 'pairs' | 'copy';

export type Step =
	| { kind: 'visit'; index: number }
	| { kind: 'compare'; left: number; right: number }
	| { kind: 'write'; index: number };

export type Measurement = {
	shape: Shape;
	n: number;
	work: number;
	extraSpace: number;
	retained: number;
	steps: Step[];
};

function checkSize(n: number): void {
	if (!Number.isSafeInteger(n) || n < 0 || n > 128)
		throw new RangeError('n must be a whole number from 0 to 128');
}

// Measure three shapes of work over n items. Every loop body adds one unit of work.
// The input itself is retained in every case; extraSpace counts only cells created
// in addition to that input.
export function measure(shape: Shape, n: number, trace = false): Measurement {
	checkSize(n);
	const steps: Step[] = [];
	let work = 0;
	if (shape === 'scan') {
		for (let index = 0; index < n; index++) {
			work++;
			if (trace) steps.push({ kind: 'visit', index });
		}
		return { shape, n, work, extraSpace: 1, retained: n, steps };
	}
	if (shape === 'pairs') {
		for (let left = 0; left < n; left++)
			for (let right = left + 1; right < n; right++) {
				work++;
				if (trace) steps.push({ kind: 'compare', left, right });
			}
		return { shape, n, work, extraSpace: 1, retained: n, steps };
	}
	const output: number[] = [];
	for (let index = 0; index < n; index++) {
		output.push(index);
		work++;
		if (trace) steps.push({ kind: 'write', index });
	}
	return { shape, n, work, extraSpace: output.length, retained: n, steps };
}

type Shape string

const (
	Scan  Shape = "scan"
	Pairs Shape = "pairs"
	Copy  Shape = "copy"
)

type Step struct {
	Kind  string
	Left  int
	Right int
}

type Measurement struct {
	Shape      Shape
	N          int
	Work       int
	ExtraSpace int
	Retained   int
	Steps      []Step
}

func checkSize(n int) {
	if n < 0 || n > 128 {
		panic("n must be a whole number from 0 to 128")
	}
}

// Measure three shapes of work over n items. Every loop body adds one unit of work.
// The input itself is retained in every case; ExtraSpace counts only cells created
// in addition to that input.
func Measure(shape Shape, n int, trace bool) Measurement {
	checkSize(n)
	steps := []Step{}
	work := 0
	if shape == Scan {
		for index := 0; index < n; index++ {
			work++
			if trace {
				steps = append(steps, Step{Kind: "visit", Left: index})
			}
		}
		return Measurement{Shape: shape, N: n, Work: work, ExtraSpace: 1, Retained: n, Steps: steps}
	}
	if shape == Pairs {
		for left := 0; left < n; left++ {
			for right := left + 1; right < n; right++ {
				work++
				if trace {
					steps = append(steps, Step{Kind: "compare", Left: left, Right: right})
				}
			}
		}
		return Measurement{Shape: shape, N: n, Work: work, ExtraSpace: 1, Retained: n, Steps: steps}
	}
	output := make([]int, 0, n)
	for index := 0; index < n; index++ {
		output = append(output, index)
		work++
		if trace {
			steps = append(steps, Step{Kind: "write", Left: index})
		}
	}
	return Measurement{Shape: shape, N: n, Work: work, ExtraSpace: len(output), Retained: n, Steps: steps}
}

05 / Try a decision

What happens when n doubles?

The exact formula is more useful than a memorised label. Predict it for 16 to 32 items, then compare your reasoning with the counts.

06 / Follow the cost

Name the bound, and say what it counts.

Here are the operations the example performs. n is the number of input items; the final row is total retained input, not extra working space.

The pairwise row is the one to earn. The first item has n − 1 later partners, the second n − 2, down to the last item’s zero. Adding that staircase gives n(n − 1) ÷ 2. At 16 items it is 120; at 32 it is 496. The ratio is 4.13, approaching four as n grows.

The copy row shows why time and space are separate axes. It writes one output per item, so the work is linear, but the output occupies n additional cells. The scan and pairwise check keep only their counter in this teaching implementation. Real values also have object headers, references, allocator behavior, and temporary storage; those details need a named runtime and a measurement rather than a made-up byte total.

07 / Give it a real job

Review a release batch before it grows teeth.

A release tool receives ids from a manifest. A one-pass check validates each id once. The check for a release listed twice is where the pairs creep in: comparing every id with every later one is the first version most people write, and at six ids it is 15 comparisons. At ten thousand it is almost fifty million, while a hash set of the ids seen so far finds the repeat in one pass. Keep the pairwise loop only where the input limit belongs in the policy, and do not let a six-item example quietly become a million-item service.

If a worker needs its own snapshot, copying is a clear ownership choice: the work remains linear and the extra retained result is also linear. If the worker only needs to read while the owner holds the batch stable, passing the input avoids that second copy. The cost table makes the trade-off visible before the API hides it behind a helper name.

08 / Make the call

Choose the smallest growth that answers the question.

Choose a single pass when each item can be decided independently. Choose pairwise work when every relationship is genuinely required and n is bounded or small. Choose a copy when the next owner needs an independent result, and name that memory in the contract.

When the operation is not the right shape, change the data structure or algorithm. A hash map can replace repeated exact-key scans, a sliding window can keep a summary as a range moves, and binary search trades sorted setup for logarithmic probes. Those lessons make the same call on a more specific requirement.

09 / Take the idea with you

Explain the cost without saying only “Big-O”.

Say what n counts, how many times the body can repeat, what memory grows, and what the bound assumes. “This visits each release id once and keeps one counter, so its work grows linearly and its extra space stays constant” is a reviewable claim. “It is O(n)” is only its short label.