TOPIC 2.12 · STUDY
Informal Run-Time Analysis
Informal run-time analysis counts how many times a statement executes. A loop body runs once for each control value that passes the test. Nested loops multiply when the inner loop finishes on every outer pass. Compare fragments by those statement-execution counts.
2.12.A
Counting statement executions
Informal run-time analysis asks how many times a statement runs, not how fast the computer is. List the control values that make the loop test true. The body executes once for each of those values. A failed final test ends the loop; it does not add another body execution.
Inclusive bounds from 1 through 5 give five body runs. A loop that starts at 0 and continues while i < 4 uses i = 0, 1, 2, and 3, so the body runs four times. A while that decreases a counter runs once for each value that still passes the test before the update.
int hits = 0;
for (int i = 1; i <= 5; i++) {
hits++; // runs for i = 1, 2, 3, 4, 5
}
// hits++ executes 5 times
int n = 4;
while (n > 0) {
System.out.print("*");
n--;
}
// print runs for n = 4, 3, 2, 1 - 4 times
Each box is one body run when i goes from 1 through 5. The total is 5 times.
In a nested loop, finish the inner loop on every outer pass before counting. If the inner body runs the same number of times on each outer pass, multiply: outer count times inner count. If the inner bound depends on the outer variable, add the completed inner counts for each outer value instead of multiplying a single fixed product.
int stamps = 0;
for (int r = 1; r <= 3; r++) {
for (int k = 1; k <= 4; k++) {
stamps++;
}
}
// outer 3, inner 4 each pass: stamps++ runs 3 * 4 = 12 times
int sum = 0;
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= i; j++) {
sum++;
}
}
// inner runs 1 + 2 + 3 + 4 = 10 times
Compare two fragments by counting the same target statement in each. Inclusive versus exclusive bounds, different step sizes, and statements placed in the outer body versus the inner body all change the totals. Whichever fragment produces the larger count for that statement runs it more times.
Key points
- Count how many times a statement executes, not how long the machine takes.
- The body runs once for each control value that passes the test.
- i from 1 through 5 means 5 executions; i < 4 from 0 means 4.
- A decreasing while runs once per successful test before the update.
- If the inner loop finishes fully on every outer pass, multiply the counts.
- Compare fragments by those statement-execution counts.
The condition that fails is not another execution of the body.