2.12 Informal Run-Time Analysis
Count statement executions from loop headers, multiply nested counts, and compare which version of a loop does less work.
- Reference Guide
- College Board Requirements
- Lesson Plan
- Code Examples
- A. Simple: Counting in Code
- Code Runner Challenge
- Hacks & Practice Tasks
- Activity 1: Count Two Statements
- Activity 2: Step Loops
- Activity 3: Same Output, Less Work
- Activity 4: Reason About Counts
- Popcorn Hack
- Code Runner Challenge
- Homework Hack
- Code Runner Challenge
- References
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++)runsb - atimes (whenb > a).for (int i = a; i <= b; i++)runsb - a + 1times.- Stepping by
s: count the valuesa, a + s, a + 2s, ...that satisfy the condition.
- Nested loops multiply: an inner statement runs
outer count * inner counttimes. - A statement inside an
ifruns 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
ntimes executes each statement in its bodyntimes. - Nested loops multiply: an outer loop of
maround an inner loop ofnruns the inner bodym * ntimes. - A loop whose variable changes by a step larger than 1 runs fewer times. Stepping by
kup tonruns aboutn / ktimes. - 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.
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");
}
}
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);
Hacks & Practice Tasks
Activity 1: Count Two Statements
The if runs on every pass. The count++ runs only when the condition is true.
How many times does statement 1 (the if check) execute?
How many times does statement 2 (count++) execute?
Activity 2: Step Loops
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.
Activity 4: Reason About Counts
What are the minimum and maximum number of times statement 4 executes?
How many times does sum += i * j execute?
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.
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
}
}
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);
Homework Hack
Two short tasks.
- Finish the runner: predict the three counts in the comments, then add counters to check yourself.
- Answer the quick check.
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
}
}
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);
How many times does System.out.println(i + j) execute?
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.