The model
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.
A concrete walk-through
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.
Costs and failure 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.
Check your understanding
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.