Measuring Efficiency by Counting Steps

A faster computer just multiplies every step count by the same small factor. A better algorithm changes how the step count grows as n grows, and for large n that difference swamps any hardware upgrade. So instead of asking how many seconds something takes, you ask how many times a key statement runs, as a function of the number of items n. That count is what you compare across algorithms and across input sizes.

To count steps, find the statement that actually does the work and track how often it fires. A single loop over n items runs that statement n times: linear growth. Put a loop inside another loop, each running n times, and the inner statement fires n times for every one of the n outer passes, giving n times n, or n squared. A linear search through a list of 10 items checks at most 10 items, at 100 items it checks at most 100, at 1000 it checks at most 1000 — step count tracks n directly. A nested loop scales far more harshly: double n and the step count quadruples, because it depends on n squared, not n.

This step-counting habit is what lets you later sort algorithms into fast, slow, and intractable, and it sets up the comparison between two correct programs that solve the same problem differently. One might search a list in n steps, another might need n squared steps for the same job — both give the right answer, but one becomes painfully slow as n grows while the other stays manageable. Counting steps is the tool that makes that difference visible before you ever run the code.