Unit 2 · Topic 2.12

2.12 Informal Run-Time Analysis

Two pieces of code can give the same answer while doing very different amounts of work. This topic is about counting how many times a statement runs by analyzing the loops around it, which lets you compare code segments informally.

Key terms

statement execution count
tracing
run-time comparison

Statement execution counts

A statement execution count is the number of times a statement runs while the program executes. You find it by tracing, or by reasoning about the loops that surround the statement.

For a single loop, count its passes (2.8). A statement in the body runs once per pass. For for (int i = 0; i < n; i++), that's n times. If the update is i += 2, it's about half as many: for n = 10, i takes the values 0, 2, 4, 6, 8, so 5 times.

Nested loops multiply

For nested loops where the inner loop's passes don't depend on the outer variable, multiply. An outer loop with n passes around an inner loop with m passes runs the inner body n * m times. Two loops that each run n times give n * n.

When the inner loop depends on the outer variable, add up the passes one outer pass at a time. If the inner loop is for (int j = i; j < n; j++), it runs n times when i is 0, then n - 1 times, and so on down to 1. The total is n + (n - 1) + ... + 1, which equals n(n + 1) / 2. For n = 6, that's 21.

Loops in a row (not nested) add. A loop that runs n times followed by another that runs n times is 2n, not n * n.

Loops that multiply or divide

When the update doubles the variable, as in k *= 2, the variable grows fast and the loop runs only a few times. List the values: for k < 100, k takes the values 1, 2, 4, 8, 16, 32, 64, which is 7 passes. The same goes for halving a value with / 2 (as in 2.7).

Comparing code

When two code segments do the same job, the one with fewer statement executions does less work. Doubling n doubles the count of a single loop but multiplies the count of a double loop by four, so for large data the difference gets huge. You only need informal comparisons like this. Formal notation for run time isn't part of the course.

Worked examples

Try each one yourself first, then open the solution.

Example 1
Three counts for the same n
With n = 6, how many times does each of a++, b++ and c++ run? What is printed?int n = 6; int a = 0; int b = 0; int c = 0; for (int i = 0; i < n; i++) { a++; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { b++; } } for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { c++; } } System.out.println(a + " " + b + " " + c);
Show the solutionHide the solution
1. Step 1: a++ is in a single loop with 6 passes: 6 times.
2. Step 2: b++ is inside two loops that each run 6 times, and the inner one doesn't depend on i: 6 × 6 = 36 times.
3. Step 3: c++'s inner loop starts at j = i. When i = 0 it runs 6 times, then 5, 4, 3, 2 and 1. The total is 6 + 5 + 4 + 3 + 2 + 1 = 21, which matches 6 × 7 / 2.
Answer: It prints 6 36 21.
Example 2
Counting with a doubling update
How many times does count++ run?int count = 0; for (int k = 1; k < 100; k *= 2) { count++; } System.out.println(count);
Show the solutionHide the solution
1. Step 1: List the values of k for which the condition k < 100 is true: 1, 2, 4, 8, 16, 32, 64.
2. Step 2: The next value is 128, and 128 < 100 is false, so the loop stops.
3. Step 3: That's 7 values, so 7 passes.
Answer: count++ runs 7 times, and the code prints 7.
Example 3
Different updates and fixed inner loops
What is printed?int n = 10; int x = 0; int y = 0; for (int i = 0; i < n; i += 2) { x++; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= 3; j++) { y++; } } System.out.println(x + " " + y);
Show the solutionHide the solution
1. Step 1: The first loop counts i = 0, 2, 4, 6, 8 (stopping before 10), so x++ runs 5 times.
2. Step 2: The second outer loop runs 10 times (i from 1 to 10 inclusive). The inner loop always runs 3 times, whatever i is.
3. Step 3: So y++ runs 10 × 3 = 30 times.
Answer: It prints 5 30.

Common mistakes

Multiplying the counts of loops that come one after the other. Only nested loops multiply; loops in sequence add.
Assuming every nested loop is n * n. If the inner loop's bounds depend on the outer variable, add the passes row by row.
Forgetting the boundary. i <= n starting at 1 is n passes, but starting at 0 it's n + 1.

On the exam

Expect questions like "how many times is this statement executed?" Work out a small case by hand, like n = 3 or 4, and then check which answer choice's formula matches it.

Connected topics

Videos

AP CS A 4.5 - Informal Code Analysis
CodeHSWatch on YouTube (opens in a new tab)
4.5 Informal Code Analysis
Brian ZurlaWatch on YouTube (opens in a new tab)
AP CSA 4.5 Informal Code Analysis
joyceclpWatch on YouTube (opens in a new tab)
AP CS A Unit 4 Lesson 5 - Informal Code Analysis
Jacob MacMillanWatch on YouTube (opens in a new tab)

Check yourself

4 questions on 2.12 Informal Run-Time Analysis. Pick an answer to see if you got it, and why.

Question 1 of 4

Consider the following code segment.int count = 0; for (int i = 0; i < 5; i++) { for (int j = i; j < 5; j++) { count++; } }How many times is the statement count++; executed?

Question 2 of 4

Consider the following code segment.int steps = 0; for (int k = 1; k < 100; k *= 2) { steps++; }What is the value of steps after the code segment executes?

Question 3 of 4

Consider the following two code segments, where n is an int variable with the value 10.// Segment I for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { work(); } }and// Segment II for (int i = 0; i < n; i++) { work(); } for (int j = 0; j < n; j++) { work(); }How many times does each segment call work()?

Question 4 of 4

Consider the following code segment.int i = 0; int count = 0; while (i < 20) { i += 3; count++; }What is the value of count after the code segment executes?

0 of 4 answered