Informal Run-Time Analysis

Two programs can print exactly the same answer while one of them does far more work to get there. Before you can say which program is faster, you need a way to measure “work” that does not depend on how fast a particular computer happens to be. The simplest measure is to count: how many times does each statement actually run?

Until Topic 2.7, that question had a boring answer. In a program made only of statements one after another, every statement runs exactly once, from top to bottom. Loops changed that. A statement inside a loop body runs once for every pass through the loop, so a single line of code can run three times, a thousand times, or not at all.

The number of times a statement is executed while a program runs is called its statement execution count. You find it the same way you have traced loops since Topic 2.7: follow the program step by step and keep track of each time the statement runs. Once you see the pattern, you can often skip the full trace and reason about the count from the loop itself. The run time of a program is how long it takes to run. Estimating and comparing run times by counting statement executions, instead of timing programs with a stopwatch, is called informal run-time analysis.

int bodyCount = 0;
System.out.println("Ready");
int lap = 1;
while (lap <= 4)
{
    System.out.println("Lap " + lap);
    bodyCount++;
    lap++;
}
System.out.println("Done");
System.out.println("lap is now " + lap);
System.out.println("Loop body ran " + bodyCount + " times");

Ready
Lap 1
Lap 2
Lap 3
Lap 4
Done
lap is now 5
Loop body ran 4 times

The counter variable is a tool for checking your reasoning, not part of the work being measured. When you want to know how often a statement runs, put a counter increment right next to it, in the same block, and print the counter after the loop. If the printed number matches the count you worked out by hand, your reasoning was right.

The same counting works for a for loop. Remember from Topic 2.8 that the header’s three parts run at different times: the initialization once at the start, the condition before every pass, and the update after every pass.

int cheers = 0;
for (int round = 1; round <= 3; round++)
{
    System.out.println("Hip hip");
    cheers++;
}
System.out.println("Hooray!");
System.out.println("cheers is " + cheers);

Hip hip
Hip hip
Hip hip
Hooray!
cheers is 3

When a question asks how many times a statement “is executed,” it almost always means a statement in the body, and the answer is the number of passes the loop makes. The rest of this chapter is about working out that number.

int cheers = 0;
for (int round = 1; round <= 3; round++)
    System.out.println("Hip hip");
    cheers++;
System.out.println("cheers is " + cheers);

Hip hip
Hip hip
Hip hip
cheers is 1

int total = 0;
int step = 1;
while (step < 6)
{
    total += step;
    step++;
}
System.out.println(total);

Tracing every pass works, but it gets slow. A loop that runs from 1 to 500 would need a 500-row trace table. You need a faster way to get the number of passes straight from the loop header.

The idea: a counting loop’s variable steps through a list of values, and the body runs once for each value that makes the condition true. So the number of passes is the number of values in that list. Write down the first value, the last value that still passes the condition, and the step size, and count how many values that makes.

For the most common shapes, this turns into two short rules:

Why the + 1? Counting from a to b including both ends gives one more value than the difference. From 3 to 10 the difference is 7, but the values 3, 4, 5, 6, 7, 8, 9, 10 are eight numbers. Think of fence posts: a fence 7 meters long with a post every meter needs 8 posts. With <, the end value b is left out, so the extra one disappears.

int countA = 0;
for (int k = 0; k < 10; k++)
{
    countA++;
}
int countB = 0;
for (int k = 1; k <= 10; k++)
{
    countB++;
}
int countC = 0;
for (int k = 3; k <= 10; k++)
{
    countC++;
}
System.out.println("A: " + countA);
System.out.println("B: " + countB);
System.out.println("C: " + countC);

A: 10
B: 10
C: 8

The rules above are only for counting by 1. When the update is something else, such as k += 3 or timer -= 2, go back to the basic idea and list the values. The list is usually short, because big steps reach the end fast.

int countD = 0;
for (int k = 0; k < 10; k += 3)
{
    countD++;
}
int countE = 0;
int timer = 9;
while (timer > 0)
{
    timer -= 2;
    countE++;
}
System.out.println("D: " + countD);
System.out.println("E: " + countE);
System.out.println("timer is " + timer);

D: 4
E: 5
timer is -1

Loop D’s variable takes the values 0, 3, 6, 9. The next value, 12, fails k < 10, so the body runs 4 times. Loop E is a while loop counting down: the body runs when timer is 9, 7, 5, 3, and 1, which is 5 passes. After the fifth pass timer is -1, and the check -1 > 0 is false. Notice that the loop never landed on exactly 0; it stopped because the condition is timer > 0, not because timer hit a particular value.

int stars = 0;
for (int k = 0; k <= 10; k++)
{
    System.out.print("*");
    stars++;
}
System.out.println();
System.out.println(stars + " stars");

***********
11 stars

int stars = 0;
for (int k = 0; k < 10; k++)
{
    System.out.print("*");
    stars++;
}
System.out.println();
System.out.println(stars + " stars");

**********
10 stars

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

int fuel = 20;
int burns = 0;
while (fuel >= 4)
{
    fuel -= 3;
    burns++;
}
System.out.println("burns: " + burns);
System.out.println("fuel: " + fuel);

burns: 6
fuel: 2

So far, every statement in a loop body ran on every pass. Real loops are not always that simple. In Topic 2.9 you wrote loops with an if inside them, for example to count only the values that meet some condition, and in Topic 2.7 you saw that a while loop can stop after an unpredictable number of passes. In these loops, different statements have different counts, and some counts depend on the data.

Statements inside an if

An if statement inside a loop is itself a statement in the body, so its condition is checked on every pass. The statements inside the if run only on the passes where that condition is true. So you need two counts: one for the check and one for the body of the if.

int checks = 0;
int hits = 0;
for (int num = 1; num <= 30; num++)
{
    checks++;
    if (num % 3 == 0)
    {
        hits++;
    }
}
System.out.println("if condition checked: " + checks);
System.out.println("if body ran: " + hits);

if condition checked: 30
if body ran: 10

Loops whose length depends on a value

Some loops do not step by a fixed amount. This loop keeps cutting size in half with integer division until it reaches 1:

int size = 64;
int halvings = 0;
while (size > 1)
{
    size /= 2;
    halvings++;
}
System.out.println("From 64: " + halvings + " halvings");
size = 100;
halvings = 0;
while (size > 1)
{
    size /= 2;
    halvings++;
}
System.out.println("From 100: " + halvings + " halvings");

From 64: 6 halvings
From 100: 6 halvings

Starting from 64, size goes 64 → 32 → 16 → 8 → 4 → 2 → 1. That is six halvings; the check with size equal to 1 is false. Starting from 100, integer division drops the remainder each time: 100 → 50 → 25 → 12 → 6 → 3 → 1, again six halvings. Here the count is not “how big is the starting number?” but “how many times can you halve it before reaching 1?” That number grows very slowly, which will matter in 2.12.5.

int score = 120;
int passes = 0;
while (score < 100)
{
    score += 15;
    passes++;
}
System.out.println("Loop body ran " + passes + " times");
System.out.println("score is " + score);

Loop body ran 0 times
score is 120

int evens = 0;
int odds = 0;
for (int n = 10; n <= 20; n++)
{
    if (n % 2 == 0)
    {
        evens++;
    }
    else
    {
        odds++;
    }
}
System.out.println("evens: " + evens);
System.out.println("odds: " + odds);

evens: 6
odds: 5

int n = 50;
int count = 0;
while (n > 0)
{
    n /= 3;
    count++;
}
System.out.println(count);

In Topic 2.11 you put one loop inside another to work through rows and columns, or every pair of values. Nested loops are where execution counts climb quickly, and also where students most often miscount, so they deserve their own method.

The key fact from Topic 2.11: each time the outer loop’s body runs, the entire inner loop runs, from its initialization to its final false check. So if the outer loop makes 3 passes and the inner loop makes 4 passes each time, the inner body runs 4 + 4 + 4 = 3 × 4 = 12 times. A theater with 3 rows of 4 seats has 12 seats, not 7.

int seatsDone = 0;
int rowsDone = 0;
for (int row = 1; row <= 3; row++)
{
    for (int seat = 1; seat <= 4; seat++)
    {
        System.out.print("*");
        seatsDone++;
    }
    System.out.println();
    rowsDone++;
}
System.out.println("Seats printed: " + seatsDone);
System.out.println("Rows finished: " + rowsDone);

****
****
****
Seats printed: 12
Rows finished: 3

When the inner loop’s length changes

Sometimes the inner loop’s header uses the outer loop’s variable, so the inner loop makes a different number of passes each time. Multiplying no longer works. Instead, find the inner count for each outer pass and add them up.

int stars = 0;
for (int row = 1; row <= 4; row++)
{
    for (int col = 1; col <= row; col++)
    {
        System.out.print("*");
        stars++;
    }
    System.out.println();
}
System.out.println("Stars: " + stars);

*
**
***
****
Stars: 10

The inner condition is col <= row, so the inner loop runs row times:

The total is 1 + 2 + 3 + 4 = 10, and the picture shows it: each printed row is as long as that row’s inner count. If you multiplied 4 × 4 you would get 16, the count for a full square of stars, which overcounts this triangle.

int count = 0;
for (int a = 0; a < 5; a++)
{
    for (int b = 0; b < a; b++)
    {
        count++;
    }
}
System.out.println(count);

int inner = 0;
int outer = 0;
for (int i = 0; i < 10; i += 2)
{
    for (int j = 3; j > 0; j--)
    {
        inner++;
    }
    outer++;
}
System.out.println("inner: " + inner);
System.out.println("outer: " + outer);

inner: 15
outer: 5

Counting statements is useful because it lets you compare two ways of solving the same problem without running them. If two code segments give the same result, the one that executes fewer statements does less work and, informally, has a shorter run time. A second, even more useful question is how the work grows when the input gets bigger. A program that is fine for 10 values might be painfully slow for a million.

int sumA = 0;
int loopsA = 0;
for (int num = 1; num <= 100; num++)
{
    loopsA++;
    if (num % 2 == 0)
    {
        sumA += num;
    }
}
int sumB = 0;
int loopsB = 0;
for (int num = 2; num <= 100; num += 2)
{
    loopsB++;
    sumB += num;
}
System.out.println("Version A: sum " + sumA + ", loop ran " + loopsA + " times");
System.out.println("Version B: sum " + sumB + ", loop ran " + loopsB + " times");

Version A: sum 2550, loop ran 100 times
Version B: sum 2550, loop ran 50 times

Comparing at one size is a start. The bigger difference shows up when the size changes. Let n stand for the size of the problem: how many values to process, or how long a string is. The program below measures three loop shapes from this chapter at n = 10, 20, and 40: a single loop that runs n times, a nested loop that runs n times inside n times, and the halving loop from 2.12.3.

for (int n = 10; n <= 40; n *= 2)
{
    int single = 0;
    for (int i = 0; i < n; i++)
    {
        single++;
    }
    int nested = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            nested++;
        }
    }
    int halving = 0;
    int size = n;
    while (size > 1)
    {
        size /= 2;
        halving++;
    }
    System.out.println("n = " + n + ": single " + single + ", nested " + nested + ", halving " + halving);
}

n = 10: single 10, nested 100, halving 3
n = 20: single 20, nested 400, halving 4
n = 40: single 40, nested 1600, halving 5

Look at what happens each time n doubles:

Doubling n doubles both loop counts in the nested version, and 2 × 2 = 4, so its work quadruples. The halving loop barely notices: doubling the start only adds one more halving. For small inputs every version finishes almost instantly, but as n grows the nested loop falls further and further behind. This is the heart of informal run-time analysis: count the executions, and ask how the count changes as the input grows.

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

10000

This program looks at every pair of different numbers from 1 to 4 and reports the pairs whose sum is even. It has a nested loop whose inner length changes, an if inside the inner loop, and three counters. Predict all three counts before reading the trace.

int outerRuns = 0;
int innerRuns = 0;
int evenPairs = 0;
for (int first = 1; first <= 4; first++)
{
    outerRuns++;
    for (int second = first + 1; second <= 4; second++)
    {
        innerRuns++;
        if ((first + second) % 2 == 0)
        {
            System.out.println(first + " + " + second + " is even");
            evenPairs++;
        }
    }
}
System.out.println("Outer body: " + outerRuns);
System.out.println("Inner body: " + innerRuns);
System.out.println("Even pairs: " + evenPairs);

1 + 3 is even
2 + 4 is even
Outer body: 4
Inner body: 6
Even pairs: 2

• A statement execution count is how many times a statement runs. Statements outside loops run once; statements in a loop body run once per pass; a loop condition is checked one more time than the body runs.
• To find the number of passes, count the values the loop variable takes while the condition is true. Counting up by 1 from a, k < b gives b - a passes and k <= b gives b - a + 1. For other steps, list the values.
• Statements inside an if run only on the passes where its condition is true, a loop’s count can depend on changing data, and a loop whose condition starts false runs zero times.
• In nested loops, multiply when the inner loop’s length is fixed, and add the inner counts pass by pass when it changes with the outer loop.
• Compare code segments by how many statements they execute for the same input and by how that count grows as the input gets bigger; a counter variable lets you check any count you work out by hand.

for (int j = 1; j <= 5; j += 2)
{
    for (int k = 0; k < 3; k++)
    {
        System.out.print("#");
    }
    System.out.println();
}

int num = 37;
int steps = 0;
int ones = 0;
while (num > 0)
{
    if (num % 2 == 1)
    {
        ones++;
    }
    num /= 2;
    steps++;
}
System.out.println("steps: " + steps);
System.out.println("ones: " + ones);

steps: 6
ones: 3

int count = 0;
for (int row = 0; row < 3; row++)
{
    for (int col = 0; col < 5; col++)
    {
        System.out.print("o");
    }
    count++;
    System.out.println();
}
System.out.println("Inner body ran " + count + " times");

int count = 0;
for (int row = 0; row < 3; row++)
{
    for (int col = 0; col < 5; col++)
    {
        System.out.print("o");
        count++;
    }
    System.out.println();
}
System.out.println("Inner body ran " + count + " times");

String word = "letter";
int matches = 0;
for (int i = 0; i < word.length() - 1; i++)
{
    if (word.substring(i, i + 1).equals(word.substring(i + 1, i + 2)))
    {
        matches++;
    }
}
System.out.println("matches: " + matches);

String text = "rhythm and blues";
int index = 0;
int steps = 0;
while (index < text.length() && !text.substring(index, index + 1).equals("a"))
{
    index++;
    steps++;
}
System.out.println(text + " steps: " + steps);
text = "jazz";
index = 0;
steps = 0;
while (index < text.length() && !text.substring(index, index + 1).equals("a"))
{
    index++;
    steps++;
}
System.out.println(text + " steps: " + steps);

for (int i = 0; i < n; i++)
{
    for (int j = i; j < n; j++)
    {
        count++;
    }
}

Check each statement. If the answer is “not yet,” reread the linked subsection.

• I can find how many times a statement runs, and I know a loop condition is checked one more time than the body runs. Reread
• I can work out the number of passes from a loop header, including loops that count by steps other than 1. Reread
• I can count statements inside an if in a loop, loops that depend on their data, and loops that run zero times. Reread
• I can count executions in nested loops by multiplying or by adding the inner counts. Reread
• I can compare two code segments by their execution counts and describe how the counts grow as the input grows. Reread