Informal Run-Time Analysis

A counter-controlled loop with the test k <= 9 stops only after the upper endpoint has been used. Counting 4, 5, 6, 7, 8, and 9 gives six values, and hits++ runs once for each of them.

• A is not correct: 5 is the result of subtracting the endpoints without adding one; the starting value 4 is itself one of the executions.
• C is not correct: 9 is the largest value taken by k, not the number of times the body runs, because the counting starts at 4.
• D is not correct: 10 would be the count if k started at 0; here the first value is 4, so four earlier values are never used.

This is a rectangular nested loop, so the inner loop runs the same number of times for every outer-loop iteration. r takes the values 2 through 5, and c takes 0, 1, and 2. Multiply the two counts.

• A is not correct: 2 is the starting value of r rather than a count, and marks++ runs once for every inner-loop iteration.
• B is not correct: 7 comes from adding 4 and 3; for rectangular nested loops the two counts are multiplied rather than added.
• D is not correct: 15 treats the outer loop as running 5 times, but r starts at 2, so the outer loop runs 4 times.

When a question names a particular statement, count that statement rather than assuming every line has the same execution count. inside++ lies inside both loops and runs 12 times; after++ lies inside only the outer loop and runs 3 times.

• A is not correct: the two counts are printed in the order inside then after, so the larger of the two counts comes first in the output.
• C is not correct: after++ is placed after the inner loop's closing brace, so it runs once per outer-loop iteration rather than once per inner-loop iteration.
• D is not correct: 7 adds the two loop bounds instead of multiplying them, and the inner body repeats for every outer-loop iteration.

This is a triangular nested loop: the inner-loop count changes with the outer-loop variable. Because the inner test is step < level, the inner loop runs one fewer time than the value of level, so the changing counts 1, 2, and 3 are added.

• A is not correct: 3 is the number of outer-loop iterations, but count++ is inside the inner loop and runs several times per outer pass.
• B is not correct: 5 leaves out one of the changing inner counts; all three of 1, 2, and 3 have to be added.
• D is not correct: 9 assumes a rectangular pattern in which the inner loop runs 3 times for every outer-loop iteration, but the inner bound changes.

In a triangular nested loop the inner bound follows the outer-loop variable, so the inner loop runs 1 time, then 2, and so on up to n. The total inner executions are the sum of those changing counts.

• A is not correct: n is the number of outer-loop iterations by itself and ignores the repeated work that the inner loop performs on each pass.
• B is not correct: 2 * n would fit an inner loop that runs a fixed 2 times, but here the inner count changes with level.
• D is not correct: n * n describes a rectangular nested loop whose inner loop runs n times for every outer-loop iteration.

A loop with more than one condition may stop as soon as either required condition becomes false. Each pass adds 2 to seats and subtracts one from waiting. After three passes seats holds 6 and the first test fails.

• A is not correct: 4 stops the loop one pass early; when seats is 4 and waiting is 8, both tests are still true.
• C is not correct: 8 lets the body run one more time, but seats < 6 is already false once seats holds 6.
• D is not correct: 10 is the starting value of waiting rather than a value that is ever assigned to seats.

First identify the statement whose execution count is requested, then determine which loops contain it. marker++ follows the inner loop's closing brace, so it belongs to the outer loop alone, and marker holds 4 when the loops finish.

• A is not correct: 2 is the number of inner-loop iterations within a single outer pass, not the value that marker reaches overall.
• B is not correct: 6 adds the outer count 4 and the inner count 2, and neither that sum nor addition describes marker.
• C is not correct: 8 is the number of inner-body executions, which counts System.out.print(c) rather than the statement marker++.

For rectangular nested loops, the inner loop runs the same number of times for each outer-loop iteration. The total inner executions are the outer count multiplied by the inner count, so the inner body runs 5 * n times.

• A is not correct: n counts only the outer-loop iterations and ignores that the inner body repeats several times within each of them.
• B is not correct: 5 is the inner loop's count for one outer-loop iteration, not the total across all of the outer iterations.
• D is not correct: n + 5 adds the two counts, but for rectangular nested loops the two counts are multiplied instead.

A loop written as for (int i = 0; i < n; i++) runs n times when n is nonnegative. Writing a fixed value in place of n fixes the execution count, and nothing else in the program can change it.

• B is not correct: for (int i = 0; i < n; i++) runs n times, so its count depends on the value that n holds.
• C is not correct: while (x < n) gives no count on its own, since how many times it repeats depends on both values and on what changes inside.
• D is not correct: for (int i = a; i <= b; i++) runs b - a + 1 times when a <= b, so its count depends on both endpoints.

This is the informal comparison of a single loop against a nested loop. A statement inside one loop executes n times, while a statement inside a nested loop executes n * n times, and that gap widens as the input size grows.

• A is not correct: Algorithm A performs a fixed 4 operations for each record, so its repeated work grows in step with n rather than faster.
• C is not correct: the two amounts of work agree only for particular values, and as n grows the nested pattern does far more repeated work.
• D is not correct: both algorithms repeat work for each of n records; the comparison is about how much that repetition grows with the input size.