Reference Guide

Key Ideas

  • A statement execution count is the number of times one statement runs while the program runs.
  • Count from the header, not by tracing every pass:
    • for (int i = a; i < b; i++) runs b - a times (when b > a).
    • for (int i = a; i <= b; i++) runs b - a + 1 times.
    • Stepping by s: count the values a, a + s, a + 2s, ... that satisfy the condition.
  • Nested loops multiply: an inner statement runs outer count * inner count times.
  • A statement inside an if runs only on the passes where the condition is true.
  • Fewer executions usually means a faster program. Compare two versions by counting.

Quick Reference

Loop header Values of the variable Count
i = 0; i < 10; i++ 0 to 9 10
i = 1; i <= 10; i++ 1 to 10 10
i = 5; i < 10; i++ 5 to 9 5
i = 0; i < 10; i += 3 0, 3, 6, 9 4
i = 10; i > 0; i -= 2 10, 8, 6, 4, 2 5

College Board Requirements

AP CSA Unit 2, Topic 2.12: Informal Run-Time Analysis.

This lesson is built directly against the College Board’s stated learning objective for this topic:

Compute statement execution counts and informal run-time comparison of iterative statements.

Topic 2.12, Informal Run-Time Analysis, is required content on the AP Computer Science A Exam. The learning objective quoted above is the College Board’s own wording for this topic, and the activities, Popcorn Hack and Homework Hack are all written against it.


Lesson Plan

Learning Objective: Compute statement execution counts and informal run-time comparison of iterative statements.

Success Criteria: You can count how many times a statement runs from the loop header alone, multiply counts for nested loops, and say which of two versions does less work.

Tech Talk & Introduction

Informal run-time analysis means counting statement executions, not timing the program.

  • A loop that runs n times executes each statement in its body n times.
  • Nested loops multiply: an outer loop of m around an inner loop of n runs the inner body m * n times.
  • A loop whose variable changes by a step larger than 1 runs fewer times. Stepping by k up to n runs about n / k times.
  • Two versions can print identical output and do very different amounts of work.

Code Examples

A. Simple: Counting in Code

This program counts its own statement executions. Run it, then change the loop bounds and predict the new counts before running again.

Code Runner Challenge

Count executions with counters. Change the bounds and predict before running.

View IPYNB Source
// CODE_RUNNER: Count executions with counters. Change the bounds and predict before running.
public class ExecutionCounts {
    public static void main(String[] args) {
        int checks = 0;
        int hits = 0;
        for (int k = 0; k < 30; k++) {
            checks++;                 // counts the if check
            if (k % 3 == 0) {
                hits++;               // counts the body of the if
            }
        }
        System.out.println("if checked: " + checks + " times, body ran: " + hits + " times");

        int innerRuns = 0;
        for (int outer = 0; outer < 3; outer++) {
            for (int inner = 0; inner < 4; inner++) {
                innerRuns++;
            }
        }
        System.out.println("inner statement ran: " + innerRuns + " times");
    }
}
ExecutionCounts.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Hacks & Practice Tasks

Activity 1: Count Two Statements

The if runs on every pass. The count++ runs only when the condition is true.

Statement Execution Counts
Type a number for each statement.
Question 1

How many times does statement 1 (the if check) execute?

int count = 0;
for (int k = 0; k < 30; k++) {
if (k % 3 == 0) { // statement 1
count++; // statement 2
}
}
Question 2

How many times does statement 2 (count++) execute?

Activity 2: Step Loops

Stepping by 3
Predict, then count.
Nested Loops Multiply
Predict, then count.

Activity 3: Same Output, Less Work

Both loops print the multiples of 5 below n. Move the slider and compare how many times each loop’s body runs.

Compare Two Versions
Version B skips the values that never print.

Activity 4: Reason About Counts

Run-Time Questions
Three questions in the style of the AP exam.
Question 1

What are the minimum and maximum number of times statement 4 executes?

int num = (int)(Math.random() * 10);
while (num % 2 != 0) {
num = (int)(Math.random() * 10); // statement 4
}
Question 2

How many times does sum += i * j execute?

for (int i = 1; i <= 10; i++) {
for (int j = i; j <= 10; j++) {
sum += i * j;
}
}
Question 3

Which loop executes its println the fewest times?

Popcorn Hack

Rewrite the loop so it prints exactly the same numbers with far fewer passes. Keep the counter so you can prove it: the original does 135 passes.

Code Runner Challenge

Popcorn hack: same output, 27 passes instead of 135.

View IPYNB Source
// CODE_RUNNER: Popcorn hack: same output, 27 passes instead of 135.
public class FasterLoop {
    public static void main(String[] args) {
        int passes = 0;

        // TODO: rewrite this loop so it does 27 passes instead of 135
        for (int k = 0; k < 135; k++) {
            passes++;
            if (k % 5 == 0) {
                System.out.print(k + " ");
            }
        }

        System.out.println();
        System.out.println("Passes: " + passes);   // goal: 27
    }
}
FasterLoop.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Homework Hack

Two short tasks.

  1. Finish the runner: predict the three counts in the comments, then add counters to check yourself.
  2. Answer the quick check.

Code Runner Challenge

Homework: predict each count, then verify with counters. Answers: 4, 6, 3.

View IPYNB Source
// CODE_RUNNER: Homework: predict each count, then verify with counters. Answers: 4, 6, 3.
public class PredictCounts {
    public static void main(String[] args) {
        // Loop 1: how many times does the println run? Prediction: ____
        for (int i = 3; i <= 18; i += 5) {
            System.out.println("Loop 1: " + i);
        }

        // Loop 2: how many times does the println run? Prediction: ____
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < i; j++) {
                System.out.println("Loop 2: " + i + "," + j);
            }
        }

        // Loop 3: how many times does the println run? Prediction: ____
        int n = 64;
        while (n > 1) {
            n = n / 4;
            System.out.println("Loop 3: " + n);
        }

        // TODO: add int counters that count each println and print them at the end
    }
}
PredictCounts.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...
Homework Quick Check
Type a number.

How many times does System.out.println(i + j) execute?

for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j += 3) {
System.out.println(i + j);
}
}

References

College Board Course and Exam Description

Topic 2.12, Informal Run-Time Analysis, is required content on the AP Computer Science A Exam. The learning objective quoted in section 3 (College Board Requirements) is the College Board’s own wording for this topic, and the activities, Popcorn Hack and Homework Hack are all written against it.

Outside Academic Reference

Counting statement executions is the informal form of the standard analysis of iterative algorithms, where cost is expressed as a count of elementary operations rather than elapsed time.

Reference List

College Board. (2025). AP Computer Science A: Course and exam description. https://apcentral.collegeboard.org/courses/ap-computer-science-a

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th ed.). MIT Press.

All Java lessons