2.12 Informal Run-Time Analysis

2.12 Informal Run-Time Analysis

A statement execution count is the number of times a particular statement runs while a program executes. Counting executions gives us a practical way to estimate how much work a program performs without measuring seconds on a specific computer.

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

Essential Knowledge 2.12.A.1: A statement execution count indicates the number of times a statement is executed by the program. Statement execution counts are often calculated informally through tracing and analysis of the iterative statements.

The suggested skill is 4.A — Describe the behavior of a code segment or program. In this topic, describing behavior means more than predicting the final value of a variable: you explain how many times important statements execute and how the structure of selection and iteration controls that work.

Counting work by tracing

Tracing means following a program step by step, recording changing variable values and noting when statements execute. For an iterative statement, inspect its starting condition, repetition condition, update operation, and body. The loop’s execution pattern—not the number of lines visible on the screen—determines the count.

Consider a program that processes five temperature readings:

int total = 0;

for (int reading = 1; reading <= 5; reading++) {
    total += reading;
}

System.out.println(total);

The body statement total += reading; executes once for each value of reading: $1$, $2$, $3$, $4$, and $5$. Its statement execution count is therefore $5$. The println statement executes once, after the loop, and the final value printed is $15$.

A useful trace is:

Pass	reading at start	Body executes?	total after body
1	$1$	Yes	$1$
2	$2$	Yes	$3$
3	$3$	Yes	$6$
4	$4$	Yes	$10$
5	$5$	Yes	$15$
6	$6$	No	$15$

The condition is checked again when reading becomes $6$, but the body does not execute then. This distinction matters: checking a loop condition is not the same as executing the loop body. If a question asks for the count of the body statement, count only the successful passes.

Selection changes the count

A selection statement can cause a statement inside a loop to execute fewer times than the loop itself:

int positiveCount = 0;

for (int value = 1; value <= 6; value++) {
    if (value % 2 == 0) {
        positiveCount++;
    }
}

The for loop body is reached $6$ times. The condition value % 2 == 0 is evaluated $6$ times, but positiveCount++ executes only for the even values $2$, $4$, and $6$, so its execution count is $3$. Informal run-time analysis must identify which statement is being counted.

Misconception check — “The loop runs six times, so every statement inside it runs six times.”
False. A statement inside an if block runs only when the condition is true. A statement inside an else block has a different count, and a statement outside the loop may execute just once.

Comparing iterative behavior

Informal run-time analysis becomes especially useful when comparing iterative statements. Suppose one loop increases its control variable by $1$, while another increases it by $2$:

for (int index = 0; index < 10; index++) {
    System.out.println(index);
}

for (int index = 0; index < 10; index += 2) {
    System.out.println(index);
}

The first output statement executes $10$ times, for indices $0$ through $9$. The second executes $5$ times, for indices $0$, $2$, $4$, $6$, and $8$. Both loops have the same stopping boundary, but the update operation changes their execution counts.

For larger inputs, this difference affects informal run-time comparison. If an input size is represented by $n$, a loop that advances through every item performs roughly $n$ body executions. A loop that examines every other item performs roughly $n/2$ body executions. These are informal comparisons: they describe relative work without requiring a precise timing experiment.

A reliable tracing procedure

When describing a code segment or program, use this sequence:

1. Identify the exact statement whose execution count is requested.
2. Record the loop variable’s initial value.
3. List the values that satisfy the loop condition.
4. Account for any if condition that can skip the statement.
5. Count successful executions, not merely condition checks.
6. State the resulting behavior, including important output or variable changes.

This process connects informal run-time analysis directly to the Unit 2 thematic area, Selection and Iteration. Selection determines which statements execute; iteration determines how many opportunities those statements receive.

Retrieval check: In the following loop, how many times does count++ execute?

int count = 0;

for (int number = 3; number <= 12; number += 3) {
    if (number > 6) {
        count++;
    }
}

The loop visits $3$, $6$, $9$, and $12$. The condition is true for $9$ and $12$, so count++ executes $2$ times and count ends with the value $2$. That is 4.A — Describe the behavior of a code segment or program through a statement execution count.