How do you count how many times a statement executes in a loop, including nested loops?
Topic 4.5 Informal Code Analysis: determine the number of times a statement executes in a loop or nested loop by counting iterations, without using formal big-O notation.
A focused answer to AP CSA Topic 4.5, covering how to count statement executions in single and nested loops, the effect of step size and start/end bounds, conditional statements inside loops, and triangular versus rectangular counts, with a fully worked counting example.
Reviewed by: AI editorial process; not yet individually human-reviewed
Have a quick question? Jump to the Q&A page
Jump to a section
What this topic is asking
The College Board (Topic 4.5) wants you to perform informal code analysis: determine how many times a particular statement executes in a loop or nested loop. This is "informal" because it does not use formal big-O notation - you simply count iterations exactly. You must account for the start value, the stopping condition, and the step size of each loop, and for nested loops you combine the inner and outer counts.
Counting a single loop
List the values the control variable takes, and count them. The step size matters:
for (int i = 0; i < n; i++)runsntimes.for (int i = 0; i < n; i += 2)runs aboutn / 2times - list the even values 0, 2, 4, ... belown.for (int i = n; i > 0; i--)runsntimes, counting down.
The effect of bounds
The start value and whether the condition uses < or <= change the count. for (int i = 1; i <= n; i++) runs n times; for (int i = 1; i < n; i++) runs n - 1 times. Always pin down both endpoints.
Conditional statements inside loops
For example, a statement guarded by if (i % 2 == 0) inside a loop over i = 0 ... 9 runs only for the even values 0, 2, 4, 6, 8 - five times, not ten.
Nested loops: multiply or sum
For nested loops, multiply the counts when the inner bound is independent of the outer variable, and sum them when it depends on it (the triangular case from Topic 4.4). This is the most heavily tested counting scenario:
- Rectangular: inner runs
ktimes each ofmouter passes, totalm * k. - Triangular: inner runs
1, 2, ..., nacross the outer passes, totaln(n+1)/2.
Try this
Q1. How many times does the body of for (int i = 0; i < 20; i += 5) execute? [1 point]
- Cue. Four times -
itakes the values 0, 5, 10, 15 (20 fails the condition).
Q2. Explain why a statement guarded by if (i % 3 == 0) inside a loop over i = 0 ... 9 runs fewer times than the loop iterates. [2 points]
- Cue. The statement runs only on iterations where
iis a multiple of 3 (0, 3, 6, 9), so 4 times, even though the loop iterates 10 times.
Exam-style practice questions
Practice questions written in the style of College Board exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.
AP 2022 (style)1 marksMultiple choice. How many times does the statement `count++` execute?
```java
int count = 0;
for (int i = 0; i < 10; i = i + 3) {
count++;
}
```
(A) `4`
(B) `3`
(C) `10`
(D) `9`
(E) `5`
Show worked answer →
The answer is (A).
The control variable i starts at 0 and increases by 3 each pass, so it takes the values 0, 3, 6, 9 - all less than 10. The next value would be 12, which fails i < 10, so the loop stops. That is 4 iterations, so count++ runs 4 times. (B) misses one of the values; (C) and (D) ignore the step size of 3.
Markers reward listing the control-variable values (0, 3, 6, 9) and counting them, rather than assuming a step of 1.
AP 2020 (style)3 marksFree response (code writing). Write a method `header` named `public static int countExec(int n)` that returns the number of times the innermost statement of the following structure would execute, for a given `n`, by actually running equivalent loops and counting. The structure to model: an outer loop with `i` from 0 to n-1, and for each `i` an inner loop with `j` from 0 to i-1.
Show worked answer →
A 3-point question testing iteration counting expressed as code.
public static int countExec(int n) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
count++;
}
}
return count;
}
Point 1: the outer loop runs i from 0 to n - 1. Point 2: the inner loop runs j from 0 to i - 1, so it executes i times on outer pass i. Point 3: count accumulates 0 + 1 + 2 + ... + (n-1), the triangular total, and is returned. For example countExec(4) returns 0 + 1 + 2 + 3 = 6. Using j < n instead of j < i would give the wrong, rectangular count.
Related dot points
- Topic 4.4 Nested Iteration: write and trace nested loops, where an inner loop runs in full on each pass of an outer loop, and count the total number of inner-loop iterations.
A focused answer to AP CSA Topic 4.4, covering nested loops, how the inner loop completes fully on each outer pass, counting total iterations (including triangular patterns where the inner bound depends on the outer variable), and tracing nested output, with a fully worked example.
- Topic 4.2 for Loops: use a for loop, whose header combines initialisation, a boolean condition and an update, to repeat a block a controlled number of times, and convert between for and while loops.
A focused answer to AP CSA Topic 4.2, covering for-loop header syntax (init; condition; update), the order in which the three parts run, counting iterations, equivalence with while loops, common patterns, and tracing, with a fully worked example.
- Topic 4.1 while Loops: use a while loop to repeat a block of statements while a boolean condition remains true, with correct initialisation, condition and update to avoid infinite or off-by-one loops.
A focused answer to AP CSA Topic 4.1, covering while loop syntax, the initialise/test/update pattern, why each loop control variable must change, infinite loops and off-by-one errors, and how to trace iterations, with a fully worked example.
- Topic 4.3 Developing Algorithms Using Strings: traverse a String with a loop using length, substring and indexOf to implement standard algorithms such as counting characters, searching for a pattern and building a new String.
A focused answer to AP CSA Topic 4.3, covering String traversal with a for loop, extracting one character with substring, the standard counting, searching and accumulation patterns, the half-open index range, and bounds safety, with a fully worked example.
- Topic 1.3 Expressions and Assignment Statements: evaluate arithmetic expressions using operator precedence, integer division and the modulo operator, and assign results to variables.
A focused answer to AP CSA Topic 1.3, covering arithmetic operators, operator precedence, integer division truncation, the modulo operator, and how assignment statements store results, with a fully traced worked evaluation.
Sources & how we know this
- AP Computer Science A Course and Exam Description — College Board (2025)