The Cost Model: Counting Basic Steps

Why not just use a stopwatch?

You now know what an algorithm is, you can read pseudocode calmly, and you can tell a decision problem from an optimization one. The natural next question is: how do we say one algorithm is better than another? The obvious idea is to run both and time them with a stopwatch. That answer is tempting and almost completely useless for design.

A stopwatch measures one program, on one machine, for one input, on one day. Change the laptop, the language, the compiler, or what else is running, and the number changes. Worse, a clever algorithm that loses on tiny inputs can win enormously on large ones, and a single timing tells you nothing about how the cost will grow. We want a verdict about the algorithm itself, not an accident of hardware.

So we trade the stopwatch for a thought experiment. We invent an idealized machine, agree on which operations count as one unit of work, and then count those units as a function of the input size n. The result is a machine-independent cost: a formula that describes the algorithm, not your laptop. That formula is what the whole field is built on.

The RAM machine and the basic step

The standard idealized machine is the RAM model (Random-Access Machine). Picture a single processor with an unlimited bank of numbered memory cells, each holding one number, each reachable in the same amount of time regardless of its address. The processor reads, writes, does one arithmetic or comparison, follows a branch, or calls a routine. Each such elementary action is one basic step, and we declare every basic step to cost exactly 1 unit of time.

So what counts as one step? A safe rule of thumb: anything that operates on a constant amount of data and does not loop. Adding two numbers, comparing two numbers, assigning a value to a variable, indexing into an array A[i], evaluating an if-condition, following a goto — each is one step. A whole loop is NOT one step; it is the sum of the steps of its iterations. A function call is one step for the call itself, plus whatever happens inside.

Counting: a worked micro-example

Counting steps is just careful bookkeeping. Take the most basic task: find the largest value in an array A of n numbers by scanning once. Let us walk through it and add up the steps, the way you would on paper.

best = A[0]                 // 1 step
for i = 1 to n-1:          // loop runs n-1 times
    if A[i] > best:        // 1 compare each pass
        best = A[i]        // 1 assign, sometimes
return best                // 1 step

1. The setup line best = A[0] runs once: 1 step.
2. The loop runs n-1 times. Each pass does the comparison A[i] > best: that is n-1 comparisons, so about n steps from comparing alone.
3. The assignment best = A[i] runs only when we find a new maximum — somewhere between 0 and n-1 times. Either way it is at most n-1 more steps.
4. The final return is 1 step. Add the loop's own counter increments and tests, which are also one each per pass.
5. Total: a constant, plus a constant times n. That is c1 * n + c2 for some constants. We summarize it as O(n) — linear time.

Notice what we did NOT do: we did not fret over whether a comparison really costs the same as an assignment, or whether the loop counter is exactly one step. Those choices change the constants c1 and c2 but never the shape of the answer, which stays proportional to n. That is the point of the model — it lets us be lazy about constants on purpose, and still get the right scaling.

Loops, nested loops, and reading the time off the code

Most of counting a running time is counting how many times loops run. A single loop from 1 to n that does a constant amount of work per pass costs Theta(n). The skill that does the real damage is nested-loop analysis: when a loop sits inside another loop, you multiply the iteration counts. An outer loop over n, each pass running an inner loop over n, does roughly n times n = n^2 units of work — that is Theta(n^2).

Be careful: not every nested loop is n^2. If the inner loop runs only 1, 2, 3, ..., n times across the outer passes, the total is the sum from i=1 to n of i, which equals n(n+1)/2 — still Theta(n^2), but with a constant of one half, a detail the O-notation will hide. By contrast, an inner loop that halves a range each time — like the step inside binary search — runs only about log n times, which is why halving is the secret behind so many fast algorithms.

Which input? Worst, best, and average

There is one loose end. The step count often depends on which input of size n you feed in, not just on n. Searching a list for a value might stop at the first element (lucky) or scan all n (unlucky). So 'the cost as a function of n' is not yet a single number — it is a whole range of values across all inputs of that size. We tame this with three lenses.

The worst case is the most steps over all inputs of size n — the pessimist's guarantee, the one we cite most because it is a promise no input can break. The best case is the fewest steps, often a fluke we should not rely on. The average case is the mean over inputs of size n, which is genuinely useful but carries a catch: it depends entirely on which distribution of inputs you assume. Assume a different distribution and the average changes. The next guide unpacks all three carefully.

Two honest warnings before you go. First, the hidden constants we threw away are real: Big-O describes scaling, not a verdict at every size, so an O(n log n) method can genuinely lose to an O(n^2) one on small inputs where the constants dominate. Asymptotics speak about large n. Second, counting basic steps measures time; the same RAM model lets you count memory cells used for space, and a fast algorithm is not automatically a small one. Keep both meters running.