What Algorithms Are — Problems, Models & Correctness

basic step

A basic step is one unit of work that we agree to count as costing the same fixed amount, no matter how the input grows. When we say an algorithm "takes about n steps," we have to be clear about what a step is — otherwise the count means nothing. The trick is to pick simple operations, each of which truly takes a bounded amount of time, and then just count how many of them the algorithm performs. It is like estimating a road trip's length by counting fence-posts that are evenly spaced: each post is one unit, so counting posts measures distance.

In the standard RAM model, the basic steps are the primitive operations that each cost one unit: reading or writing one memory cell, a single arithmetic operation (add, subtract, multiply, divide) on word-sized numbers, one comparison, one assignment, and following one branch or jump. The key property is that each is bounded — it does not get more expensive as n grows. So a single line like "m = A[i]" is a constant number of basic steps, and a loop "for i = 1 to n" that does a constant amount of work each pass performs about n basic steps in total. We deliberately do not chase the exact count of every micro-operation; we count the basic steps that dominate, which is enough to see how the running time scales.

What counts as basic is a modelling choice, and choosing well keeps the analysis honest. Treating one comparison as a basic step is fine for sorting numbers that fit in a word, but comparing two thousand-character strings is not really one step — it can take time proportional to the string length, and pretending otherwise would understate the true cost. The art is to choose basic steps whose cost is genuinely bounded for the problem at hand. Get that right and counting steps gives a faithful picture; get it wrong and a hidden, growing cost can creep in unnoticed.

In "for i = 1 to n: total = total + A[i]", each pass does one read, one addition, one assignment — a constant number of basic steps — so the whole loop is about n basic steps, i.e. linear time.

Constant work per pass, n passes, n basic steps total.

A basic step must have bounded cost. Comparing two short numbers is one step; comparing or copying long strings or big integers is not — its cost grows with their length, and counting it as "one step" hides real work.

Also called
primitive operationelementary operation基本操作原始操作