2.12 Informal Code Analysis

TLDR

Informal run-time analysis in AP Computer Science A means counting how many times statements run, especially inside loops, by tracing through the code. You figure out a statement execution count, then compare iterative statements to see which one does more work as the input grows. This is mostly a tracing-and-counting skill, not memorizing formal Big O rules.

more resources to help you study

practice multiple choiceFRQ practice & scoringcheatsheetsscore calculator

Why This Matters for the AP Computer Science A Exam

This topic builds the habit of describing what a code segment actually does, step by step. On the multiple-choice section, you may be asked to determine the result of a code segment or how many times a statement runs for given input, and careful counting of loop iterations is exactly what those questions test. The same tracing skill helps you check your own loops when you write free-response code, since you can confirm a loop runs the right number of times instead of one too many or one too few.

Run-time comparison here is informal. You are counting executions and comparing iterative statements, not proving formal complexity. Keep your reasoning grounded in tracing.

Key Takeaways

• A statement execution count is the number of times a statement runs during a program. You usually find it by tracing the loops.
• A single loop over n items runs its body about n times, so the count grows in step with the input size.
• Nested loops multiply: if both loops depend on n, the inner statement can run on the order of n times n.
• Triangular nested loops, where the inner loop bound depends on the outer variable, run 1 + 2 + 3 + ... which totals n(n+1)/2.
• Operations outside any loop run a fixed number of times no matter how big the input is.
• Trace with a small sample input and an actual count when you are unsure. Counting beats guessing.

How to Count Statement Executions

Start by asking: how many times does this exact line run? Use a trace table or a small value of n and count.

Single Loops

A single loop that visits each element once runs its body once per element.

</>Java
// Body runs array.length times
public int findMax(int[] array) {
    int max = array[0];
    for (int i = 1; i < array.length; i++) {  // runs array.length - 1 times
        if (array[i] > max) {
            max = array[i];
        }
    }
    return max;
}

If the array has n elements, the loop body runs n - 1 times. The count grows directly with n.

Nested Loops

When one loop sits inside another, multiply the iteration counts.

</>Java
// Inner statement runs n * n times
public void printAllPairs(int[] array) {
    for (int i = 0; i < array.length; i++) {      // n iterations
        for (int j = 0; j < array.length; j++) {  // n iterations each
            System.out.println(array[i] + ", " + array[j]);
        }
    }
}

With n elements, the inner print runs n times n times, so the execution count grows much faster than a single loop.

Triangular (Dependent) Nested Loops

Not every nested loop runs the full n times on the inside. Watch the inner loop's bounds.

</>Java
public int countPairs(int[] array) {
    int count = 0;
    for (int i = 0; i < array.length; i++) {
        for (int j = i; j < array.length; j++) {  // runs n, then n-1, then n-2 ...
            count++;
        }
    }
    return count;
}

The inner loop runs n times, then n - 1, then n - 2, and so on. Adding those gives n(n+1)/2 total inner executions. That still grows quickly, but it is about half of n times n, so counting carefully matters.

Sequential Loops

Loops that run one after another add their counts. They do not multiply.

</>Java
public void processArray(int[] array) {
    for (int i = 0; i < array.length; i++) {  // n executions
        array[i] *= 2;
    }
    for (int i = 0; i < array.length; i++) {  // n more executions
        System.out.println(array[i]);
    }
}

The total body executions here are about n + n, not n times n. Side by side means add; nested means multiply.

Comparing Iterative Statements

Informal comparison means lining up two pieces of code and asking which one runs its inner statement more times as the input grows.

</>Java
// Loop A: single pass
for (int i = 0; i < n; i++) {
    System.out.println(i);          // runs n times
}

// Loop B: nested pass
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println(i + j);  // runs n * n times
    }
}

For a small n the two might feel similar, but as n grows, Loop B's inner statement count pulls far ahead. That gap is the whole point of an informal run-time comparison: you are predicting which code does more work without timing it on a computer.

How to Use This on the AP Computer Science A Exam

Code Tracing

When a question asks how many times a statement runs, trace it with a concrete value of n.

• Write down the loop control variable's value on each pass.
• Mark when the Boolean condition becomes false, since that controls when the loop stops.
• For nested loops, finish the inner loop completely before the outer loop advances.

Counting Checklist

• Find the most-repeated statement, usually the innermost loop body.
• Count how many times each loop runs, then multiply nested loops and add sequential loops.
• Check the inner loop's bounds. A bound like j = i or j < i means a triangular count, not a full n by n.
• Verify the start and end values to avoid an off-by-one count.

Common Trap

A loop header like for (int i = 1; i <= n; i++) runs n times, but for (int i = 0; i < n; i++) also runs n times. The difference is the starting value and the comparison operator. Trace the boundaries instead of assuming, because being off by one changes your execution count.

Common Misconceptions

• Every nested loop is not automatically n times n. If the inner loop bound depends on the outer variable, the count can be n(n+1)/2 or smaller. Read the bounds before deciding.
• Sequential loops do not multiply. Two loops one after another add their counts; only nested loops multiply.
• A statement execution count is a real number you can calculate by tracing, not a vague label. For this topic, count the executions rather than reaching for formal Big O notation.
• The loop body does not always run at least once. If the Boolean condition is false at the start, a while or for loop body runs zero times.
• More lines of code does not mean a higher execution count. A single statement inside a deeply nested loop can run far more often than many statements that sit outside loops.

Related AP Computer Science A Guides

• 2.1 Algorithms with Selection and Repetition
• 2.7 While Loops
• 2.6 Equivalent Boolean Expressions
• 2.11 Nested Iteration
• 2.8 For Loops
• 2.10 Developing Algorithms Using Strings