2.12 Informal Run-Time 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.

Informal run-time analysis means counting how many times a statement runs, mostly by tracing loops. Multiple-choice questions may ask for the result of a code segment or how many times a statement runs for a given input, and the same counting lets you check that your own free-response loops don't run one time too many or too few.

How Loop Structure Sets Statement Execution Counts

• 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.

Tracing Loops to Count Statement Executions

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

• Misconception: Every nested loop is n times n.
  Actually: 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.
• Misconception: Sequential loops multiply.
  Actually: Sequential loops do not multiply. Two loops one after another add their counts; only nested loops multiply.
• Misconception: A statement execution count is a vague label, not a number you can calculate by tracing.
  Actually: 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.
• Misconception: The loop body always runs at least once.
  Actually: 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.
• Misconception: More lines of code means a higher execution count.
  Actually: 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