Interview prompt
Explain a practical method for analyzing algorithms to an engineer who understands the surrounding system but has not used this technique. Walk from its contract to a concrete operation, then discuss where it fails or becomes expensive.
A strong answer
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.
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.
A complete answer also calls out the assumptions that control correctness. 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.
Close by describing one representative test or measurement. 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.
Follow-up questions
Answer the follow-ups in the frontmatter. Use the linked article for the concept and the trace to make the explanation concrete.