Recap
A statement execution count is the number of times a statement runs. It is found by tracing and analysing the loops, and it is used to compare the work done by different code.
For for (int i = 0; i < n; i++) { body }:
| Part | Count |
|---|---|
| Initialization | 1 |
| Boolean expression | n + 1 |
| Body | n |
| Update | n |
Key relationships
| Code shape | Innermost statement runs |
|---|---|
| Single loop, i from 0 to n - 1 | n |
Step 2 (i += 2) |
about n / 2 |
Doubling (i *= 2) or halving (n = n / 2) |
about log2 n (for n = 1000, 9 halvings) |
| Nested, independent bounds | n x m |
Nested, inner j < i |
n(n - 1) / 2 |
Nested, inner j <= i for i from 1 to n |
n(n + 1) / 2 |
Early exit (a return inside the loop) |
between a best case and a worst case |
When n doubles: a single loop does 2 times the work, an n x n nested loop about 4 times, a halving loop one more pass.
Assumptions
- Only the named statement is counted unless the question says otherwise.
- Each iteration of the body counts as one execution of each statement in it.
- Counts assume the loop reaches its natural end unless an exit is described.
Mistakes to avoid
- Counting tests as equal to body runs (it is one more).
- Multiplying the bounds when the inner bound depends on the outer variable.
- Forgetting an early return that reduces the count.
- Reading
i *= 2as if it added 2. - Using the formula for a triangle (n(n + 1) / 2) when the inner loop starts at
i + 1. - Comparing two algorithms using a single input, instead of seeing how counts grow.
Worked mini-example
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < 4; j++) {
count++;
}
}The inner loop always runs 4 times, whatever i is, so count++ runs 4n times. For n = 10 that is 40; for n = 20 it is 80, so doubling n doubles the work. If the inner bound were j < n, the count would be n x n: 100 for n = 10 and 400 for n = 20, so doubling n would quadruple the work. The only difference between the two segments is the inner bound: whether it is a fixed number or uses n.
Quick self-check
- How many times does the body of
for (int i = 5; i <= 50; i += 5)run? Answer: 10 (5, 10, …, 50). - How many times is the condition of
for (int i = 0; i < 8; i++)evaluated? Answer: 9. - An algorithm finds the first multiple of 7 in a sequence and stops. When is its work smallest? Answer: when the first value is already a multiple of 7.
- If n doubles, by what factor does an n x n loop’s work change? Answer: 4.
Full explanations and diagrams are in the Topic 2.12 study guide.