Nested
Iteration

Master loops inside loops: understand how nested iteration works, trace execution counts, and build powerful patterns in Java.

AP Computer Science A

What Is Iteration?

Iteration means repeating a block of code multiple times using a loop. In Java, the most common loops are the for loop and the while loop. A single loop lets you repeat an action \( n \) times.

for (int i = 0; i < 5; i++) {
    System.out.println(i);
}

What Is Nested Iteration?

Nested iteration is when you place one loop inside another. The inner loop runs completely for every single iteration of the outer loop. This is how you process grids, tables, and multi-dimensional data.

for (int row = 0; row < 3; row++) {        // outer loop
    for (int col = 0; col < 4; col++) {    // inner loop
        System.out.print("* ");
    }
    System.out.println();
}

Visualizing Execution Flow

The Iteration Count Rule

The total number of times the inner body executes in a nested loop is the product of the iteration counts of each loop:

Outer: \( m \) times

The outer loop controls how many "passes" occur

Inner: \( n \) times

The inner loop runs completely each pass

Total: \( m \times n \)

Body executes \( m \times n \) total times

A restorer repairs a luminous pixel mosaic

A restorer lifts a tile from a luminous rectangular mosaic.

Grid algorithms turn a visual pattern into explicit row and column operations. Bounds checks determine which neighboring cells can be accessed.

Trace a 4-by-5 nested loop

A 4-by-5 grid numbers all 20 visits from left to right across successive rows.

Four outer-loop iterations each run five inner iterations: 20 body executions in row-major order. The inner counter is initialized four times.

Why This Matters: \( O(n^2) \)

When both loops iterate \( n \) times, the inner body runs \( n \times n = n^2 \) times. This means nested loops often produce quadratic time complexity.

Independent vs Dependent Inner Loop

	Independent	Dependent
Inner bound	Fixed constant (e.g., col < 5)	Uses outer variable (e.g., col < row)
Inner count	Same every pass	Changes each pass
Total iterations	\( m \times n \)	\( \frac{n(n-1)}{2} \) (triangular)
Pattern shape	Rectangle	Triangle
Time complexity	\( O(n^2) \)	\( O(n^2) \)

Dependent Loop: Triangle Pattern

for (int row = 1; row <= 5; row++) {
    for (int col = 1; col <= row; col++) {
        System.out.print("* ");
    }
    System.out.println();
}

How to Trace Nested Loops

1

Identify the outer loop bounds. Determine how many times the outer loop iterates and what variable it controls.

2

Identify the inner loop bounds. Check: is the inner bound a constant (independent) or does it use the outer variable (dependent)?

3

Build a trace table. For each outer iteration, list the inner variable values and what the body produces.

4

Count total executions. Multiply (independent) or sum the series (dependent) to find the total body execution count.

5

Check for print vs println. print stays on the same line; println moves to the next line: this controls the output shape.

Example 1: Rectangle Output

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

Outer: 3 iterations

i = 0, 1, 2: produces 3 rows

Inner: 4 iterations

j = 0, 1, 2, 3: prints 4 symbols per row

Output:
# # # #
# # # #
# # # #

Total: \( 3 \times 4 = 12 \) print statements.

Example 2: Number Grid

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

Example 3: Accumulator in Nested Loops

int sum = 0;
for (int i = 1; i <= 3; i++) {
    for (int j = 1; j <= 4; j++) {
        sum += j;
    }
}
System.out.println(sum);  // What prints?

1

i = 1: inner adds j = 1+2+3+4 = 10. sum = 10

2

i = 2: inner adds 1+2+3+4 = 10 again. sum = 20

3

i = 3: inner adds 1+2+3+4 = 10 again. sum = 30

Nested Loops and 2D Arrays

The most important use of nested iteration in AP CSA is traversing 2D arrays. The outer loop selects the row, and the inner loop selects the column.

int[][] grid = { {1,2,3}, {4,5,6} };

for (int r = 0; r < grid.length; r++) {
    for (int c = 0; c < grid[r].length; c++) {
        System.out.print(grid[r][c] + " ");
    }
    System.out.println();
}

Output:
1 2 3
4 5 6

grid.length = number of rows. grid[r].length = number of columns in row r. This is the standard row-major traversal pattern.

Row-Major vs Column-Major

Row-Major

Outer loop: rows. Inner loop: columns. Visits left-to-right, top-to-bottom. Most common.

Column-Major

Outer loop: columns. Inner loop: rows. Visits top-to-bottom, left-to-right. Less common but tested.

// Column-Major traversal
for (int c = 0; c < grid[0].length; c++) {
    for (int r = 0; r < grid.length; r++) {
        System.out.print(grid[r][c] + " ");
    }
}

For grid {{1,2,3},{4,5,6}}, column-major prints: 1 4 2 5 3 6. Notice the outer loop variable c is the column, and we still access grid[r][c] with row first.

Common Mistakes

Off-by-One Errors

Using < vs <= or starting at 0 vs 1 changes the iteration count. Always trace the boundary values.

Wrong Variable in Body

Accidentally printing or accumulating the outer variable i when you meant the inner variable j, or vice versa.

Misplaced println()

Placing println() inside the inner loop (too many newlines) or forgetting it after the inner loop (everything on one line).

Nested Iteration Summary

	Key Idea	Formula / Pattern
Independent loops	Inner bound is constant	\( m \times n \) iterations
Dependent loops	Inner bound uses outer var	\( \frac{n(n \pm 1)}{2} \) iterations
Row-major 2D	Outer = row, Inner = col	grid[r][c], left-to-right
Column-major 2D	Outer = col, Inner = row	grid[r][c], top-to-bottom
Time complexity	Two nested loops of size n	\( O(n^2) \)

Question 1 of 5

How many times does the inner print statement execute?

for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 3; j++) {
        System.out.print("X");
    }
}

The outer loop runs 5 times, the inner loop runs 3 times each pass. Total: \( 5 \times 3 = 15 \).

Question 2 of 5

What is the output of this code?

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

This is a dependent loop: j goes from 1 to i. When i=1, prints "1". When i=2, prints "1 2". When i=3, prints "1 2 3". Each row ends with println().

Question 3 of 5

What value of sum is printed?

int sum = 0;
for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 2; j++) {
        sum++;
    }
}
System.out.println(sum);

The inner body runs \( 4 \times 2 = 8 \) times. Each execution increments sum by 1, so sum = 8.

Question 4 of 5

Which traversal order visits elements top-to-bottom within each column before moving to the next column?

Column-major traversal uses the column index as the outer loop variable. This processes all rows in column 0 first, then all rows in column 1, and so on: top-to-bottom, left-to-right.

Question 5 of 5

How many total iterations does the inner loop body execute?

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

This is a dependent loop where j starts at i. When i=1: j runs 4 times. i=2: 3 times. i=3: 2 times. i=4: 1 time. Total: \( 4+3+2+1 = 10 \).

NestedIteration

What Is Iteration?

What Is Nested Iteration?

Visualizing Execution Flow

The Iteration Count Rule

A restorer repairs a luminous pixel mosaic

Trace a 4-by-5 nested loop

Why This Matters: \( O(n^2) \)

Independent vs Dependent Inner Loop

Dependent Loop: Triangle Pattern

How to Trace Nested Loops

Example 1: Rectangle Output

Example 2: Number Grid

Example 3: Accumulator in Nested Loops

Nested Loops and 2D Arrays

Row-Major vs Column-Major

Common Mistakes

Nested Iteration Summary

Question 1 of 5

Question 2 of 5

Question 3 of 5

Question 4 of 5

Question 5 of 5

Nested
Iteration