2.12 Informal Run-Time Analysis

What you need to know

• Statement execution count is the number of times a particular statement runs. It's the exam's measure of efficiency.
• A single loop of n iterations executes its body n times. Nested loops multiply. Sequential loops add.
• Comparing algorithms: fewer executions for the same input size = more efficient. The exam gives two versions and asks which is better or by how much.
• Loops that halve their range each time (binary search) run about log₂ n times; loops that check every element run n times; comparing all pairs runs about n².
• Early exit (return when found) reduces the count in the best case but not the worst.
• The count can depend on the input, not just its size: searching for the first element takes 1 step; the last takes n.

Worked example

// Version A
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        count++;                // runs n * n times
    }
}
// Version B
for (int i = 0; i < n; i++)
{
    count++;                    // runs n times
}
for (int j = 0; j < n; j++)
{
    count++;                    // runs n times
}
// B runs 2n times total. For n = 100: A = 10,000, B = 200.

Going deeper

The nuance, edge cases, and connections that turn a 3 into a 5.

• The exam's efficiency measure is statement execution count — how many times a given statement runs for an input of size n — not clock time and not formal Big-O (though the ideas align).
• Counting rules: a loop with k iterations runs its body k times. Nested independent loops: multiply. Nested dependent loops: sum the series. Sequential loops: add. An if inside a loop: the condition runs every iteration; the body runs only when true.
• Common growth patterns and what produces them: constant — no loop; linear (n) — one loop over n; quadratic (n²) — two nested loops over n; logarithmic (log n) — a loop that halves its range (binary search); n log n — merge sort.
• Best vs. worst case: a search with early exit takes 1 step if the target is first, n if it's last or absent. "How many comparisons" questions specify the input; if they say "maximum" or "worst case," assume the target is last or missing.
• Comparing two implementations: the one with fewer statement executions for the same n is more efficient. The exam gives two versions and a specific n, and asks for the counts or which is better.
• Efficiency isn't everything: for small n, the simpler algorithm may be preferable. But the exam's questions are about the counts, not the judgment call.

Mistakes that cost points

• Counting loop headers as body executions. The condition check runs one more time than the body (the failing check).
• Assuming an if body runs every iteration. Only when the condition is true. If the question gives the data, count.
• Treating early-exit as always fast. Worst case is still n.

Practice questions

Written in the style of the real exam. Try each one before revealing the answer.

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