AP Computer Science A · Unit 2 lecture · Part 11 of 12 · 8 min

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

Mr. Thompkins
Two programs can give the same answer and take wildly different amounts of time. You don't need a stopwatch to compare them. You just count how many times the important statement runs.

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?
Pair the ends: 1 + n, 2 + (n - 1), and so on. Every pair adds to n + 1, and there are n / 2 pairs, so the total is n(n + 1) / 2. For n = 5: 5 × 6 / 2 = 15. For n = 100: 5050.
none loopnested, j from 0nested, j from ihalving
4416102
8864363
16162561364
1001001000050506
How many times the innermost statement runs for four loop shapes. Halving means while (n > 1) { n /= 2; }.
0246810020406080100nstatement executionsn × nn(n + 1) / 2n
The same counts as n grows, computed for n = 0 to 10. Nested loops grow much faster than a single loop.

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?
Integer division: both sides are ints, so the decimal part of 12.5 is thrown away. That's why the halving loop goes 25, 12, 6, 3, 1 instead of 25, 12.5, and so on.
Pause and think
for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { count++; } } How many times does count++ run when n is 5?
I thought about it. Show me
10. For i = 0, 1, 2, 3, 4, the inner loop runs 0, 1, 2, 3 and 4 times, and 0 + 1 + 2 + 3 + 4 = 10. In general that's n(n - 1) / 2.
Count the executions

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++;
}
  1. 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.
  2. Add them: 5 + 4 + 3 + 2 + 1 = 15. (Check with the formula: n(n + 1) / 2 with n = 5 is 15.)
  3. 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
  1. For Segment I, how many j values are there when i is 0? When i is 1?
  2. Add up the inner counts: 5, 4, 3, 2, 1.
  3. For Segment II, write m after each halving until it reaches 1.
Check yourself
How many times does the statement x++ execute?
for (int a = 0; a < 6; a++)
{
    for (int b = 0; b < 6; b += 2)
    {
        x++;
    }
}
  1. A15
  2. B18
  3. C20
  4. 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.

Exam tip from Mr. T

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.