Nested loops and iteration patterns

Learning objectives

• Trace a complete inner loop for each outer-loop iteration.
• Count the work in rectangular and triangular nested-loop patterns.
• Express the input-size model behind a simple complexity claim.
• Recognize that break exits only the innermost enclosing loop or switch.

Prerequisites: counted loops and conditions. Review Loops and Conditions. Arrays are a later application, not a prerequisite for the examples here.

What makes a loop nested?

A nested loop is a loop whose body contains another loop. The inner loop normally completes all of its iterations before the outer loop advances. Think of the outer loop as choosing a row and the inner loop as visiting columns in that row.

#include <iostream>

int main() {
    for (int row{1}; row <= 2; ++row) {
        for (int column{1}; column <= 3; ++column) {
            std::cout << '(' << row << ", " << column << ") ";
        }
        std::cout << '\n';
    }
}

Trace the execution

The inner body runs 2 × 3 = 6 times. If there are r rows and c columns and each inner iteration does constant work, the traversal takes O(r × c) time. This model counts body executions; it does not claim a fixed number of seconds.

Triangular iteration pattern

#include <iostream>

int main() {
    for (int row{1}; row <= 4; ++row) {
        for (int column{1}; column <= row; ++column) {
            std::cout << '*';
        }
        std::cout << '\n';
    }
}

The inner body runs 1 + 2 + 3 + 4 = 10 times. With n rows, the count is n(n + 1) / 2, which grows quadratically; therefore the time complexity is O(n²) when each body execution does constant work.

Scope, break, and common mistakes

• Declare the inner-loop counter in the inner for; it is initialized again for each outer iteration.
• Put the newline after the inner loop when each outer iteration should produce one output row.
• For zero-based positions, use index < size, not index <= size.
• A break inside the inner loop exits that inner loop only; it does not automatically stop the outer loop.
• Do not assume every nested loop is quadratic: count the actual number of inner iterations.

Practice

1. How many inner-body executions occur for 6 rows and 7 columns?
2. How many stars are printed by the triangular pattern with 5 rows?
3. What is the complexity of a rectangular traversal with r rows and c columns, assuming constant work per cell?
4. If a break runs in the inner loop, which loop ends?

Worked answers

Summary

Trace the entire inner loop before advancing the outer loop. Rectangular nested loops multiply iteration counts; triangular loops sum a changing count. State the input dimensions and work-per-iteration assumptions whenever you give a complexity result.

References

• cppreference: for statement
• cppreference: break statement