5 · Loop-analysis rules & space complexity

Quick rules for nested and halving loops, plus how much memory an algorithm uses.

In one sentence

To get the running time of iterative code, work inside-out: multiply the work inside a loop by how many times the loop runs, add consecutive blocks, and take the bigger branch of an if/else. Space complexity counts the extra memory the algorithm needs as $n$ grows.

Everyday analogy

Nested loops = a clock. The minute hand (inner loop) goes all the way round 60 times for every one step of the hour hand (outer loop). Total minute-steps in 12 hours = $12 \times 60$ . When the inner loop's length depends on the outer one, you can't multiply; you add up the rounds instead (a sum).

Space = desk space while doing homework. The textbook is the input (you'd have it anyway). Space complexity asks how much scratch paper you need, and whether it grows with the size of the problem.

The four rules

Rule	Code shape	Time
1. Loop	`for` $n$ times { body }	$n \times$ (time of body)
2. Nested loops	analyse inside-out	product of the loop sizes (if independent)
3. Consecutive statements	block A; block B	time(A) + time(B), so the bigger one wins
4. If/else	`if` test `then` S1 `else` S2	test + max(S1, S2) for the worst case

Loop patterns to recognise instantly

Pattern	Iterations	Growth
`for i ← 1 to n`	$n$	$\Theta(n)$
`for i ← 1 to n` / `for j ← 1 to n`	$n^2$	$\Theta(n^2)$
`for i ← 1 to n` / `for j ← 1 to i`	$\frac{n(n+1)}{2}$	$\Theta(n^2)$
`i ← 1; while i < n: i ← 2i`	$\lceil\log_2 n\rceil$	$\Theta(\log n)$
`i ← n; while i > 1: i ← i/2`	$\approx\log_2 n$	$\Theta(\log n)$
`for i ← 1 to n` / doubling `j` loop inside	$n\log_2 n$	$\Theta(n\log n)$
`i ← n; while i ≥ 1: (do i work); i ← i/2`	$n + \frac n2 + \frac n4 + \dots \approx 2n$	$\Theta(n)$
three nested loops $i < j < k$	$\frac{n(n-1)(n-2)}{6}$	$\Theta(n^3)$

Dependent nested loop as a staircase (for i ← 1 to n / for j ← 1 to i), with $n = 5$ :

i=1  ■
i=2  ■ ■
i=3  ■ ■ ■
i=4  ■ ■ ■ ■
i=5  ■ ■ ■ ■ ■        15 squares = 5·6/2  → about half of the 5×5 square → Θ(n²)

Doubling loop (i ← 1; while i < n: i ← 2i), with $n = 100$ :

iteration	1	2	3	4	5	6	7
$i$ after	2	4	8	16	32	64	128 ≥ 100, stop

7 iterations, and $\lceil\log_2 100\rceil = 7$ ✓

Halving outer loop with inner work $i$ (looks like $n\log n$ but isn't):

i = n     ■■■■■■■■■■■■■■■■  (16)
i = n/2   ■■■■■■■■          (8)
i = n/4   ■■■■              (4)
i = n/8   ■■                (2)
i = 1     ■                 (1)      total 31 = 2n − 1 → Θ(n)

Common mistakes

Multiplying loop sizes when the inner bound depends on the outer variable. Write the sum instead.
Seeing two nested loops and automatically saying $n^2$ . The halving-outer pattern above is $\Theta(n)$ .
Forgetting the recursion stack in space analysis.
Counting the input array itself as extra space. Space complexity usually means auxiliary space; say which one you mean.

Mastery check

Solve without hints, then explain each step

i ← n
while i ≥ 1 do
    for j ← 1 to i do
        x ← x + 1
    i ← ⌊i / 2⌋

(a) How many times does x ← x + 1 run when $n = 16$ ? (b) Give $\Theta(\cdot)$ in general. (c) What is the extra space?

Your mastery check

Not started

Solve the problem above with no hints, close the page and explain it out loud. Tick each step honestly.

Solved the mastery check with no hints

Said it in one sentence

Explained it with my own analogy

Walked through the steps of my own hand trace

Explained why it is correct / how fast it is

Named a trap a beginner would fall into

Status

Tick all six steps to unlock “Mastered”.

Which study mode worked for you?

Saved in this browser onlySee all my progress →

References

Lecture06 Algorithm Analysis: Slides 3–4 (the four rules), 5–9 (loop examples).
04 Correctness & Space: Slides 6–9 (space complexity: fixed vs. variable part, arrayMax).
03 Algorithm Analysis: Slides 7–8 (a triple-nested brute-force loop).
CLRS 4e §2.2 (analysing algorithms), Appendix A (sums used for loops).

5 · Loop-analysis rules & space complexity

Everyday analogyCopy Anchor Link

The four rulesCopy Anchor Link

Loop patterns to recognise instantlyCopy Anchor Link

Common mistakesCopy Anchor Link

Mastery checkCopy Anchor Link

✅ Answers