How to Count Nested Loops Correctly (and the 2 Mistakes Almost Everyone Makes)

Markbackcs — Sat, 24 Oct 2026 15:09:14 +0000

"Two loops, so it's n². Done."

For the Big O, that's true. But if your course asks you to count the operations, the assignments, the tests and so on, this is exactly where most students lose marks. Not because it's hard, but because two small things are easy to miss.

So let's count one together, slowly, with pictures.

The algorithm

FOR i ← 1 to n DO
    FOR j ← 1 to n DO
        K
    END FOR
END FOR

We'll count four things:

Assignments: setting the loop variables, i ← 1 and j ← 1
Tests: checking the loop condition, "is i still ≤ n?"
Iterations: moving the loop variable on, i ← i + 1 and j ← j + 1
Execution: how many times K actually runs

First, the big picture

Before counting anything, picture what's happening.

Every time the outer loop runs once, the inner loop runs all the way through. So with n = 3, you get 3 rows of 3, and K runs 9 times.

Keep this picture in mind. It explains every count below: anything inside the outer loop happens once per outer pass.

The one rule to remember

A loop from 1 to n doesn't check its condition n times. It checks it n + 1 times.

With n = 3, the loop checks i = 1, 2 and 3, and all three pass. Then it checks i = 4. That check fails, and that's what ends the loop. But it still happened, so it still counts.

1. Assignments

" width="799" height="373">

The outer loop sets i ← 1 once.
The inner loop sets j ← 1 every time it starts, and it starts once per outer pass, so n times.

Assignments = 1 + n

2. Tests

" width="800" height="400">

The outer loop checks its condition n + 1 times.
On each of the n outer passes, the inner loop checks n + 1 times.

So the inner loop's tests are n(n + 1), not n + 1.

Tests = (n + 1) + n(n + 1) = (n + 1)²

Notice the last row of the picture: when the outer check fails (i = 4), the outer loop stops, and the inner loop never starts. That's why the inner checks are multiplied by n, not by n + 1.

3. Iterations

Same idea, but now we count how many times each loop moves forward:

i moves on n times.
j moves on n times per outer pass, so n · n = n² times.

Iterations = n + n²

4. Execution

Go back to the grid. K runs once in every cell:

Execution = n · n = n²

If your course uses summations, this is written as a double sum: the outer sum over i, the inner sum over j.

Putting it together

T(n) = (1 + n) + (n + 1)² + (n + n²) + n²

Expand (n + 1)² = n² + 2n + 1, collect the terms, and you get:

T(n) = 3n² + 4n + 2 ∈ O(n²)

Always check with a small n

This takes one minute and catches almost every mistake. Pick n = 2 and count each part by hand:

Assignments: 1 + 2 = 3
Tests: (2 + 1)² = 9
Iterations: 2 + 4 = 6
Execution: 2² = 4

That's 22 in total, and the formula gives 3(4) + 8 + 2 = 22. ✓

The 2 mistakes almost everyone makes

Mistake 1: adding the inner loop instead of multiplying it.

The inner loop isn't something that happens once, next to the outer loop. It happens inside it, on every pass. So its counts get multiplied by the number of outer passes.

Mistake 2: forgetting the check that fails.

Every loop has one extra check at the end, the one that fails and stops the loop. Leave it out, and every count that involves tests is off.

Bonus: when the inner loop starts at i

What changes if the inner loop is FOR j ← i to n instead?

" width="800" height="427">

Now the inner loop runs n times, then n − 1, then n − 2, all the way down to 1. Instead of a full square, you get a triangle:

n + (n − 1) + … + 1 = n(n + 1) / 2

It's about half the work, but it still grows like n², so it's still O(n²).

Try these yourself

Count the tests for FOR i ← 1 to n with FOR j ← 1 to 2n inside it.
How many times does K run if the inner loop is FOR j ← 1 to i?
Three nested loops, each from 1 to n: how many times does the innermost statement run?

Answers

Outer: n + 1. Inner: 2n + 1 per pass, over n passes. Total: (n + 1) + n(2n + 1) = 2n² + 2n + 1.
1 + 2 + … + n = n(n + 1) / 2.
n · n · n = n³.

The takeaway

Two ideas get you through almost every nested loop question:

Anything inside the outer loop happens once per outer pass, so multiply.
A loop from 1 to n tests n + 1 times, because the check that fails still counts.

Write the four headings, Assignments, Tests, Iterations and Execution, before you start counting, and check your answer with n = 2 before you move on.

I lost marks on exactly this kind of counting myself, which is a big part of why I started making animated lessons that build these counts step by step, one line at a time. If you'd like to watch this one in motion, the lesson on analysing nested loops is free to watch, no account needed: Analysing Nested Loops on Markback

And if a loop question has you stuck, drop it in the comments. I'm happy to count it through with you.

DEV Community: Markbackcs