DEV Community

Cover image for How to Count Nested Loops Correctly (and the 2 Mistakes Almost Everyone Makes)
Markbackcs
Markbackcs

Posted on

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

#algorithms #beginners #computerscience #tutorial

"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

A nested loop and the four things we'll count.

FOR i ← 1 to n DO
    FOR j ← 1 to n DO
        K
    END FOR
END FOR
Enter fullscreen mode Exit fullscreen mode

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.

Each row is one pass of the outer loop. Inside each row, the inner loop runs from 1 to n.

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

Three checks pass, then one more check fails and ends the loop.

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

i is set once. j is set again at the start of every outer pass.<br>

  • 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

The outer loop checks n + 1 times. On each of its n passes, the inner loop checks n + 1 times too.<br>

  • 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

Add the four counts and simplify.

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

Count by hand for n = 2, then compare with the formula.

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?

Now each row is one shorter than the one before.<br>

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

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

Answers

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

The takeaway

Two ideas get you through almost every nested loop question:

  1. Anything inside the outer loop happens once per outer pass, so multiply.
  2. 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.

Top comments (0)