An algorithm is a step-by-step instruction that solves a problem in bounded time; its cost is measured by counting primitive operations — the small steps whose duration does not depend on the input size.

The definition carries a requirement that is easy to read past: bounded time. A recipe that might never finish is not an algorithm. That is why analysis is not an afterthought — a procedure has to terminate, and the interesting question is immediately how fast.

To answer "how fast" without a stopwatch, you count the steps the machine has to take. The steps that count are the ones with constant cost — they take the same time whether the array has ten elements or ten million:

• evaluating an expression
• assigning a value to a variable
• indexing into an array
• calling a method
• returning from a method

Each is taken as costing one unit. The unit is a fiction — an array index and a method call are not really equally expensive — but it is a harmless fiction, because the whole apparatus of the O-notation is about to throw away constant factors anyway.

Tip: the test for "is this primitive?" is does its cost depend on n? a[i] = b is primitive; sort(a) is not.

Go deeper:

• Analysis of algorithms — cost models — how a “step” gets defined, and when the uniform cost model stops being honest.

A measurement describes one machine on one input; an operation count describes the algorithm itself, which is the only thing you can carry to another machine or a bigger input.

Timing has three problems that counting does not:

1. It measures the wrong thing. A stopwatch measures your CPU, your compiler, your JIT warm-up, what else the OS was doing. Change any of those and the number changes, while the algorithm did not.
2. It only covers the inputs you tried. The interesting behaviour is what happens as the input grows, and you cannot try all sizes.
3. It needs an implementation. Counting works on pseudo-code, so you can compare two designs before writing either one.

Counting gives a function of the input size, e.g. $8n - 2$, and a function can be extrapolated: it predicts the shape of the curve at sizes you never measured. That predictive power is the point of the whole exercise — asymptotic analysis is about the trend, not about any single number.

Measurement still has a job — it is how you confirm the predicted shape actually shows up in the real implementation — but it is the check, not the analysis.

Go deeper:

• MIT 6.100L — Big Oh and Theta (Ana Bell) — a full lecture on describing growth independently of machine and implementation.