1.2Counting loop iterations
The idea
To find the running time of loops, count how many times the innermost statement runs and express it in n.
Think of it like this: Counting the steps of a staircase walk: sometimes you take every stair, sometimes you double your stride.
Why it exists
Loop counting is the most common 1 or 2 mark question on complexity.
How it works
- A loop i = 1..n adds n. A loop i *= 2 adds log₂ n.
- Independent nested loops multiply.
- If the inner bound depends on i, write the sum: Σ i = n(n + 1)/2.
- A doubling outer loop with an inner loop up to i gives 1 + 2 + 4 + … + n ≈ 2n = Θ(n).
Worked example: for i = 1, 2, 4, …, n: for j = 1..i
Inner loop runs i times for each i, so the total is 1 + 2 + 4 + … + n = 2n − 1 = Θ(n), not n log n.
Now play with it
- →Switch the loop nest and read the count row for n = 8 … 1024.
- →Look at the ratio row: it tells linear (2), quadratic (4) or log (1) immediately.
| n | 8 | 16 | 32 | 64 | 128 | 256 | 1024 |
|---|---|---|---|---|---|---|---|
| executions of x++ | 36 | 136 | 528 | 2,080 | 8,256 | 32,896 | 5,24,800 |
| count at n / count at n/2 | - | 3.78 | 3.88 | 3.94 | 3.97 | 3.98 | 4.00 |
Reading the ratio row: ≈ 2 means linear, ≈ 4 quadratic, ≈ 2.1 with a slowly falling value means n log n, ≈ 1 means logarithmic.
Check yourself
for (i = 1; i <= n; i *= 2) for (j = 1; j <= i; j++) x++; takes
Exam notes (the dense version)
Multiply nested loop counts when they are independent. A loop that doubles (i *= 2) runs log n times. A loop whose inner bound depends on the outer index gives a sum: 1 + 2 + … + n = n(n + 1)/2 = Θ(n²), but 1 + 2 + 4 + … + n = Θ(n). A loop with i * i <= n runs √n times; i = √i runs log log n times.
Previous year questions: Asymptotic Analysis & Recurrences (16)
PYQs are grouped by topic, so this is the full set for Asymptotic Analysis & Recurrences; try the ones that match this subtopic. Open all 16 on the topic page.