2.12 Informal run-time analysisCounting how much work a loop does

A statement execution count is the number of times a particular statement runs. Informal run-time analysis means comparing algorithms by those counts: the one that runs its key statement fewer times does less work. On the exam you'll be asked "how many times does this line execute?" for loops, nested loops and loops with unusual updates.
Three rules cover almost everything. One loop that runs n times executes its body n times. Nested loops with fixed bounds multiply: an outer loop of n passes around an inner loop of m passes runs the inner body n × m times. When the inner bound depends on the outer variable, add up the inner passes row by row instead.
?Wait, how do I add 1 + 2 + ... + n quickly?
| n | one loop | nested, j from 0 | nested, j from i | halving |
|---|---|---|---|---|
| 4 | 4 | 16 | 10 | 2 |
| 8 | 8 | 64 | 36 | 3 |
| 16 | 16 | 256 | 136 | 4 |
| 100 | 100 | 10000 | 5050 | 6 |
Loops that don't count by 1 need care. A loop that halves its variable, like while (n > 1) { n /= 2; }, runs only a handful of times even for big n: 6 times for 100, because 100 goes to 50, 25, 12, 6, 3 and 1. A loop that counts by 3 runs about a third as many times as one that counts by 1. When in doubt, list the values for a small case.
?Wait, why does 25 / 2 give 12?
I thought about it. Show me
How many times does count++ run in each segment?
Segment I
for (int i = 0; i < 5; i++)
{
for (int j = i; j < 5; j++)
{
count++;
}
}
Segment II
int m = 64;
while (m > 1)
{
m /= 2;
count++;
}- Segment I: the inner loop runs from j = i up to 4. That's 5 passes for i = 0, then 4, 3, 2 and 1.
Why?
The number of j values from i to 4 is 5 - i. - Add them: 5 + 4 + 3 + 2 + 1 = 15. (Check with the formula: n(n + 1) / 2 with n = 5 is 15.)
- Segment II: list m after each pass: 32, 16, 8, 4, 2, 1. That's 6 passes, and then 1 > 1 is false.
Why?
Each pass halves m, so the count is how many halvings take 64 down to 1: 64 is 2 to the 6th power.
Answer: Segment I: 15. Segment II: 6.
Stuck? Get a hint
- For Segment I, how many j values are there when i is 0? When i is 1?
- Add up the inner counts: 5, 4, 3, 2, 1.
- For Segment II, write m after each halving until it reaches 1.
for (int a = 0; a < 6; a++)
{
for (int b = 0; b < 6; b += 2)
{
x++;
}
}- A15
- B18
- C20
- D24
Show the answer
B. The outer loop runs 6 times (a = 0 to 5). The inner loop runs 3 times each (b = 0, 2, 4, then 6 fails b < 6). 6 × 3 = 18. Choice D counts the inner loop as 4 passes, and choice C uses 5 outer passes with 4 inner ones.

For execution counts, never guess from the shape of the code. Write the outer variable's values in a column and the number of inner passes next to each one, then add the column. It takes a minute and it's exact.