2.12 Informal Run-Time Analysis

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.