Informal Run-Time Analysis
Skill 4.A
Big idea: Run-time analysis means counting how many times a statement executes. Fewer executions for the same result means a more efficient algorithm.
- Calculate statement execution counts and informal run-time comparison of iterative statements.
Counting executions
For a single loop, count the values the loop variable takes. For nested loops with independent bounds, multiply. When the inner bound depends on the outer variable, add up each pass.
a++runs once per outer pass: 5.b++runs 5 × 4 = 20 times.c++runs 5 + 4 + 3 + 2 + 1 = 15 times.
int a = 0, b = 0, c = 0;
for (int i = 0; i < 5; i++) {
a++;
for (int j = 0; j < 4; j++) {
b++;
}
}
for (int i = 0; i < 5; i++) {
for (int j = i; j < 5; j++) {
c++;
}
}
System.out.println(a + " " + b + " " + c);5 20 15Comparing two approaches
Both loops find the same sum of 1..n, but one does far less work. For an n of 1000, the first runs its body 1000 times and the second does one calculation.
int n = 1000;
int sum1 = 0;
for (int i = 1; i <= n; i++) sum1 += i;
int sum2 = n * (n + 1) / 2;
System.out.println(sum1 + " " + sum2);500500 500500- A statement execution count is how many times a statement runs.
- Independent nested loops: multiply outer × inner.
- Dependent inner bounds: add up each pass.
- Count the loop condition checks separately from the body if the question asks; the condition runs one extra time (the final false check).
- Plug in a small n (2 or 3), count by hand, then match the pattern to the answer choices.
How many times does the inner body run?
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= i; j++)
count++;Show answer
10 (1 + 2 + 3 + 4).