This trace follows the actual state transitions behind the companion A Practical Method for Analyzing Algorithms. It describes a common execution path; implementation details can vary, so keep the contract separate from the mechanism.
Step 1: Choose the input-size measure
An analysis begins by naming the input size and the operation whose growth matters. Counting every source line is rarely useful: a loop body may perform one comparison, scan another collection, or invoke a routine with its own cost. Write the dominant work as a sum, then simplify only after the cost model is clear.
Step 2: Count primitive operations
For nested loops over an n by n grid, the inner body runs n squared times. If the inner loop instead halves its range on every pass, its work is logarithmic and the total is n log n. A recurrence makes divide-and-conquer costs explicit: split, solve subproblems, and combine their results.
Step 3: Compose repeated work
For independent nested loops, multiply their iteration counts; when an inner range shrinks, sum its changing costs instead of multiplying by the first count.
At this point, record the state that changed and check the invariant before advancing. If the operation repeats, make clear which values persist and which are recomputed.
Step 4: Separate growth cases
Big-O suppresses constants and lower-order terms; it does not predict wall-clock latency. Average-case analysis needs an input distribution, while amortized analysis bounds a sequence of operations. Keep worst-case guarantees separate from expected behavior and from measurements on one machine.
Step 5: Compare with the workload
Analyze a routine with two nested loops where the inner loop doubles its index. State the input size, number of iterations, and an input that reaches the worst case.
The trace is complete when the result satisfies the stated contract. Compare this model with the concrete runtime or system you are studying before making a performance claim.