2.12 - Informal Run-Time Analysis

A statement execution count is just how many times a specific statement actually runs during the program. Usually you figure this out informally, by tracing through the loop by hand and counting.


// how many times does the print statement run?
for (int i = 0; i < 10; i++) {
    System.out.println(i); // this runs exactly 10 times
}

// nested loop execution count: outer runs 3 times, inner runs 4 times each
// total execution count for the print statement = 3 * 4 = 12
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 4; j++) {
        System.out.println(i + ", " + j);
    }
}

Counting Shortcuts

for (int i = a; i < b; i++) runs $b - a$ times. With <= instead of <, it runs $b - a + 1$ times. So for (int i = 1; i <= 5; i++) runs 5 times.

If the update skips by more than 1, list the values the variable takes. For example, for (int i = 0; i < 10; i += 3) runs 4 times (i is 0, 3, 6, 9).

For nested loops where the inner loop always runs the same number of times, multiply the outer count by the inner count.

A loop’s boolean expression is checked one more time than the body runs, since the last check is the false one that ends the loop. A body that runs 10 times means the condition was checked 11 times.

When the inner loop depends on the outer loop’s variable, add up the counts one outer pass at a time:


int count = 0;
for (int i = 0; i < 4; i++) {
    for (int j = i; j < 4; j++) {
        count++; // runs 4 + 3 + 2 + 1 = 10 times
    }
}
System.out.println(count); // 10

Loops that divide (or multiply) the loop variable run far fewer times:


int n = 100;
int steps = 0;
while (n > 1) {
    n = n / 2;
    steps++;
}
System.out.println(steps); // 6 (n goes 100, 50, 25, 12, 6, 3, 1)

Comparing Run Times

Execution counts let you compare two code segments that do the same job: the one that executes fewer statements does less work, so it runs faster. Both of these add up the numbers from 1 to n, but the first runs its loop body n times, while the second runs one statement no matter how big n is.


int n = 1000;

// version 1: the loop body runs n times (1,000 times here)
int sum1 = 0;
for (int i = 1; i <= n; i++) {
    sum1 += i;
}

// version 2: one statement, no loop
int sum2 = n * (n + 1) / 2;

System.out.println(sum1 + " " + sum2); // 500500 500500

Nested loops grow much faster than single loops. A single loop that runs n times does n units of work, but two nested loops that each run n times do

n^2

(n times n):

n	Single loop (n)	Nested loops ( $n^2$ )
10	10	100
100	100	10,000
1,000	1,000	1,000,000

So when n gets 10 times bigger, the single loop does 10 times more work, but the nested loops do 100 times more.

Back Next