2.11 Nested Iteration

What you need to know

• In nested loops, the inner loop runs to completion every time the outer loop's body executes.
• Total body executions = (outer iterations) × (inner iterations) when the inner bounds are fixed.
• When the inner bound depends on the outer variable (for (int j = 0; j < i; j++)), the count is a sum: 0 + 1 + 2 + … — triangular numbers.
• Output questions: track which loop controls rows vs. columns. A println after the inner loop ends the line.
• Nested loops are how you compare every pair of elements, print grids, or process 2D data (Unit 4).
• A return exits both loops (and the method). A break is not tested on the exam.

Worked example

for (int r = 1; r <= 3; r++)
{
    for (int c = 1; c <= r; c++)
    {
        System.out.print("*");
    }
    System.out.println();
}
// *
// **
// ***
// Total stars: 1 + 2 + 3 = 6

Trace it yourself

Step through with the buttons, or use the ← → keys. Changed variables are highlighted.

Going deeper

The nuance, edge cases, and connections that turn a 3 into a 5.

• Execution order: outer init → outer check → [inner init → inner check → inner body → inner update → …→ inner exit] → outer update → outer check → … Each outer iteration runs the entire inner loop from scratch, including its init.
• Independent bounds (inner doesn't depend on outer): iterations multiply. 4 × 3 = 12. Dependent bounds (inner starts or ends at the outer variable): iterations sum. for j from i to n gives n + (n−1) + … + 1 = n(n+1)/2. for j from 0 to i gives 1 + 2 + … + n.
• Output patterns: print inside the inner loop and println() after it produces rows. The outer loop counts rows; the inner counts columns. Triangles come from dependent bounds.
• Return exits everything. A return in the inner loop ends the method — both loops stop. Useful for searching a grid; a trap when tracing.
• Nested loops are the natural structure for pairs (compare every element with every other — duplicates, closest pair), grids (2D arrays in Unit 4), and substring searches (outer picks the start, inner compares characters).
• Tracing technique: write the outer variable in the margin, then the full sequence of inner values for that pass. Don't interleave in your head.
• Run-time: two nested loops over n → n² statement executions. This is what 2.12 counts and what makes some algorithms slow for large inputs.

Mistakes that cost points

• Multiplying when the bound is dependent. Sum the triangular series instead.
• Forgetting the inner loop re-initializes. j starts over on every outer pass.
• Putting println in the wrong loop. Inside the inner loop → one item per line. After it → one row per line.
• Continuing the outer loop after a return. Return ends the method.

Practice questions

Written in the style of the real exam. Try each one before revealing the answer.

for (int i = 0; i < 4; i++)
{
    for (int j = 0; j < 3; j++)
    {
        System.out.println("hi");
    }
}

for (int i = 1; i <= 4; i++)
{
    for (int j = i; j <= 4; j++)
    {
        count++;
    }
}

for (int i = 1; i <= 2; i++)
{
    for (int j = 1; j <= 3; j++)
    {
        System.out.print(i * j + " ");
    }
}