# AP® Computer Science A 2.12 Informal Run-Time Analysis

Source: https://lockincs.com/ap-csa/unit-2/2-12-informal-run-time-analysis/  
Last reviewed against the College Board Course and Exam Description (CED): 2026-11-12  
CED codes: 2.12.A, 2.12.A.1

A statement execution count is the number of times a statement is executed by a program. You calculate it informally by tracing and analyzing the iterative statements: how many times each loop runs, and how many times the inner loop runs for each outer iteration. Comparing execution counts lets you compare the run time of two code segments that do the same job.

## What you will learn

- 2.12.A Calculate statement execution counts and informal run-time comparison of iterative statements.

## 1\. What a statement execution count is

A statement execution count tells you how many times a statement is executed by the program. You usually calculate it informally, by tracing and analyzing the iterative statements 2.12.A.1. A counter variable can check your count, but on the exam you work it out by reasoning.

```
int total = 0;
for (int i = 0; i < 5; i++) {
    total += i;
}
System.out.println(total);
```

Output:

```
10
```

| Statement | Executions | Why |
| --- | --- | --- |
| `int total = 0;` | 1 | before the loop |
| `int i = 0` | 1 | initialization runs once |
| `i < 5` | 6 | true for i = 0 to 4, false for i = 5 |
| `total += i;` | 5 | once per iteration |
| `i++` | 5 | after each iteration |
| `System.out.println(total);` | 1 | after the loop |

## 2\. Counting a single loop quickly

Find the number of iterations, then the body count follows. Trace the first value, the last value that passes the check, and the step.

| Loop header | Values | Body executions |
| --- | --- | --- |
| `for (int i = 0; i < n; i++)` | 0 to n - 1 | n |
| `for (int i = 1; i <= n; i++)` | 1 to n | n |
| `for (int i = 0; i <= n; i++)` | 0 to n | n + 1 |
| `for (int i = 2; i < n; i++)` | 2 to n - 1 | n - 2 |
| `for (int i = 0; i < n; i += 2)` | 0, 2, 4, … | n / 2, rounded up |

A statement inside an `if` runs only when the condition is true:

```
int printed = 0;
for (int k = 1; k <= 20; k++) {
    if (k % 3 == 0) {
        System.out.print(k + " ");
        printed++;
    }
}
System.out.println();
System.out.println("print ran " + printed + " times");
```

Output:

```
3 6 9 12 15 18 
print ran 6 times
```

The loop body (the `if` test) ran 20 times, but the `print` ran only 6 times: once for each multiple of 3 from 1 to 20.

## 3\. Loops that double or halve

When the loop control variable doubles or halves, the count grows very slowly as the bound grows.

```
int n = 100;
int count = 0;
for (int i = 1; i < n; i *= 2) {
    count++;
}
System.out.println(count);
```

Output:

```
7
```

The values of `i` are 1, 2, 4, 8, 16, 32, 64, so the body runs 7 times. If `n` were 1000, the body would run only 10 times. A `while` loop that halves its variable behaves the same way:

```
int size = 1000;
int halvings = 0;
while (size > 1) {
    size /= 2;
    halvings++;
}
System.out.println(halvings);
```

Output:

```
9
```

`size` goes 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1 (integer division), which is 9 halvings.

## 4\. Nested loops: multiply or add up

Sequential loops add their counts; nested loops multiply them when the bounds are fixed.

```
int n = 4;
int a = 0;
int b = 0;
for (int i = 0; i < n; i++) {
    a++;
}
for (int j = 0; j < n; j++) {
    a++;
}
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        b++;
    }
}
System.out.println("sequential: " + a + ", nested: " + b);
```

Output:

```
sequential: 8, nested: 16
```

When the inner bound depends on the outer variable, add the inner count for each outer iteration:

```
int n = 5;
int count = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        count++;
    }
}
System.out.println(count);
```

Output:

```
10
```

| i | inner iterations (j < i) |
| --- | --- |
| 0 | 0 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| total | 0 + 1 + 2 + 3 + 4 = 10 |

In general this shape runs n(n - 1) / 2 times. A statement placed after the inner loop but inside the outer loop runs only n times.

## 5\. Comparing run times informally

Two code segments can produce the same result with very different execution counts. Comparing the counts is an informal run-time comparison 2.12.A.1. Both segments below count the divisors of 36.

Segment A tests every number from 1 to 36:

```
int n = 36;
int divisors = 0;
int checks = 0;
for (int d = 1; d <= n; d++) {
    checks++;
    if (n % d == 0) {
        divisors++;
    }
}
System.out.println(divisors + " divisors, " + checks + " checks");
```

Output:

```
9 divisors, 36 checks
```

Segment B only tests up to the square root, because divisors come in pairs (2 and 18, 3 and 12…):

```
int n = 36;
int divisors = 0;
int checks = 0;
for (int d = 1; d * d <= n; d++) {
    checks++;
    if (n % d == 0) {
        if (d * d == n) {
            divisors++;
        } else {
            divisors += 2;
        }
    }
}
System.out.println(divisors + " divisors, " + checks + " checks");
```

Output:

```
9 divisors, 6 checks
```

Same answer, 6 checks instead of 36. For n = 1,000,000, Segment A would make 1,000,000 checks and Segment B only 1,000. The segment with the smaller statement execution count for large inputs has the better run time.

## Common mix-ups

- Not true: The loop condition is checked the same number of times as the body runs. The Boolean expression is checked one more time than the body runs: the last check is the false one that ends the loop.
- Not true: Two loops one after the other run as many times as two nested loops. Sequential loops add (n + n), nested loops multiply (n * n). For n = 100, that is 200 versus 10,000.
- Not true: Run-time analysis needs a stopwatch. In AP® Computer Science A it is informal: count how many times statements run by tracing the loops, then compare the counts.

## In 30 seconds

- A statement execution count is how many times a statement runs.
- Find it by tracing small cases and spotting the pattern.
- Loop with n iterations: body n times, Boolean expression n + 1 times, initialization once.
- Nested loops with fixed bounds multiply; a triangle (j < i) gives 0 + 1 + ... + (n - 1) = n(n - 1) / 2.
- Steps of 2 halve the count; doubling or halving the loop control variable gives very few iterations.
- Fewer executions for the same result means a more efficient segment.

## Checkpoint: 5 practice questions

### Question 1

Consider the following code segment. How many times is the statement `System.out.println(k);` executed?

```java
for (int k = 3; k <= 30; k += 3) {
    System.out.println(k);
}
```

- A. 9
- B. 10
- C. 11
- D. 27

**Answer: B.** k takes the values 3, 6, 9, ..., 30, which are the multiples of 3 up to 30: 30 / 3 = 10 values, and 30 passes `k <= 30`. 9 forgets the last value, and 11 counts the final false check of the Boolean expression as an execution of the body.

### Question 2

Consider the following code segment. How many times is the statement `count++;` executed?

```java
int count = 0;
for (int i = 0; i < 4; i++) {
    for (int j = i; j < 4; j++) {
        count++;
    }
}
```

- A. 16
- B. 6
- C. 10
- D. 8

**Answer: C.** The inner loop starts at i, so it runs 4, 3, 2 and 1 times for i = 0, 1, 2, 3, a total of 10. 16 assumes the inner loop always runs 4 times, and 6 is the count if the inner loop started at `i + 1` (3 + 2 + 1).

### Question 3

Consider the following code segment. What is printed as a result of executing the code segment?

```java
int count = 0;
for (int i = 1; i <= 50; i *= 2) {
    count++;
}
System.out.println(count);
```

- A. 6
- B. 5
- C. 7
- D. 25

**Answer: A.** i doubles each time: 1, 2, 4, 8, 16, 32 pass `i <= 50`, and 64 fails, so the body runs 6 times. 5 forgets the starting value 1, and 25 treats the update as `i += 2`.

### Question 4

Consider the following two code segments, where `n` is a positive `int` and `count` starts at 0 in each segment. For n = 10, which of the following correctly gives the number of times `count++;` executes in each segment?

```java
// Segment I
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        count++;
    }
}

// Segment II
for (int i = 0; i < n; i++) {
    count++;
}
for (int j = 0; j < n; j++) {
    count++;
}
```

- A. Segment I: 100; Segment II: 20
- B. Segment I: 20; Segment II: 100
- C. Segment I: 20; Segment II: 20
- D. Segment I: 100; Segment II: 100

**Answer: A.** In Segment I the loops are nested, so the counts multiply: 10 times 10 = 100. In Segment II the loops run one after the other, so the counts add: 10 + 10 = 20. Mixing these up is the classic mistake; nested loops grow much faster as n grows.

### Question 5

Consider the loop header `for (int i = 0; i < 7; i++)`. How many times is the Boolean expression `i < 7` evaluated when the loop runs?

- A. 7
- B. 6
- C. 8
- D. 1

**Answer: C.** The body runs for i = 0 to 6, which is 7 iterations, and the Boolean expression is evaluated before each one. It is then evaluated one more time with i equal to 7, which is false and ends the loop: 7 + 1 = 8. 7 counts only the true evaluations, and 1 is the count for the initialization.

## Questions students ask

**What is a statement execution count?**

The number of times a statement is executed when a program runs. For a statement inside a loop, it equals the number of iterations in which that statement is reached.

**How do you count how many times a nested loop runs?**

If the bounds are fixed, multiply the outer count by the inner count. If the inner bound depends on the outer variable, list the inner count for each outer iteration and add them.

**Is Big O notation on the AP® Computer Science A exam?**

No. The course uses informal run-time analysis: counting how many times statements execute and comparing those counts.

**How many times is a for loop condition checked?**

One more time than the body runs. For a loop with n iterations the condition is evaluated n + 1 times; the last evaluation is false and ends the loop.

---

© LockInCS, licensed CC BY-NC-ND 4.0. AP® is a trademark registered by the College Board, which is not affiliated with, and does not endorse, this website.