What is an algorithm, and which operations are counted when you analyse one?
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.