2.12 Informal Code Analysis

Tracing code to find output

To predict a program's output, trace through code line by line, tracking variable values as they change. Pay close attention to loop bounds, conditionals, and how variables update each iteration. Careful hand-tracing catches off-by-one errors and helps verify whether code matches its intended purpose.

Counting iterations and operations

Informal analysis includes counting how many times a loop executes or how many times a statement runs. For nested loops, multiply the iterations of each loop. This helps estimate how a segment's work scales as input size grows, without formal Big-O notation.

Identifying errors in code segments

Look for logic errors (wrong output despite running), infinite loops (missing or wrong update to the loop condition variable), and off-by-one errors (using `<` vs `<=`, wrong starting index). Comparing expected vs. actual traced values reveals where code deviates from its intended behavior.

Key terms

Tracing code

Manually stepping through a program line by line, tracking variable values, to determine its output or behavior.

Infinite loop

A loop whose terminating condition never becomes false, often due to a missing or incorrect update statement.

Off-by-one error

An error where a loop runs one too many or too few times, often from incorrect comparison operators or starting index.

Nested loop iteration count

Multiply the number of iterations of the outer loop by the number of iterations of the inner loop to find total executions.

Logic error

Code that runs without crashing but produces incorrect output because it doesn't match its intended purpose.

Try an AP-style question

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        x++;

How many times does x++ run?

1. n²
2. n + n
3. 2n
4. n