How Nested Loops Execute (EK 2.11.A.1)

When one loop is nested inside another, the inner loop must complete all of its iterations before the outer loop can advance to its next iteration. This is the single most important rule for nested loops, and it is stated directly in the CED. Think of it like a clock: the inner loop is the seconds hand, the outer loop is the minutes hand — seconds complete a full revolution before minutes advance by one.

for (int outer = 0; outer < M; outer++) {
    // runs M times total

    for (int inner = 0; inner < N; inner++) {
        // runs N times per outer iteration
        // runs M * N times total
    }

    // outer body continues after inner loop completes
}

for (int i = 1; i <= 3; i++) {
    for (int j = 1; j <= 2; j++) {
        System.out.print("(" + i + "," + j + ") ");
    }
    System.out.println();  // new line after each outer iteration
}

// Output:
// (1,1) (1,2)
// (2,1) (2,2)
// (3,1) (3,2)

// Total inner body executions: 3 * 2 = 6

Counting Total Executions

The total number of times the inner loop body executes is the product of the number of outer iterations and the number of inner iterations per outer pass. When the inner loop bound depends on the outer variable, you must sum, not multiply.

// Outer runs 5 times, inner runs 4 times per outer iteration
// Total: 5 * 4 = 20 inner body executions
for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 4; j++) {
        System.out.print("* ");
    }
}

// Inner bound depends on outer variable
// i=1: j runs 1 time | i=2: 2 times | i=3: 3 times | i=4: 4 times
// Total: 1+2+3+4 = 10 inner body executions
for (int i = 1; i <= 4; i++) {
    for (int j = 1; j <= i; j++) {
        System.out.print("* ");
    }
    System.out.println();
}
// Output:
// *
// * *
// * * *
// * * * *

Common Nested Loop Patterns

for (int row = 1; row <= 5; row++) {
    for (int col = 1; col <= 5; col++) {
        System.out.printf("%4d", row * col);
    }
    System.out.println();
}
// 1  2  3  4  5
// 2  4  6  8 10
// 3  6  9 12 15 ...

// Count pairs (i,j) where i < j and both divisible by 3
int count = 0;
for (int i = 1; i <= 20; i++) {
    for (int j = i + 1; j <= 20; j++) {   // j starts at i+1 to avoid duplicates
        if (i % 3 == 0 && j % 3 == 0) {
            count++;
        }
    }
}
System.out.println(count);  // 10

// WRONG: both loops use i — inner loop modifies outer's variable
for (int i = 0; i < 3; i++) {
    for (int i = 0; i < 3; i++) {  // compile error: i already declared
        System.out.print(i + " ");
    }
}
// Use different variable names: i for outer, j for inner

Real-World Connection

Nested iteration is the engine behind 2D data processing. Image processing loops over every row and column of pixels. Matrix multiplication requires triple-nested loops. Generating all pairs of items for comparison (duplicate detection, closest-pair problems) uses nested loops. In Unit 4, you will use nested loops to traverse 2D arrays — the outer loop handles rows, the inner loop handles columns within each row.

Summary

• Inner loop completes all iterations before outer loop advances. (EK 2.11.A.1)
• Independent bounds: total = outer × inner iterations.
• Dependent bounds: total = sum of inner iterations across each outer value.
• Variable names: use distinct variables (e.g., i and j) for outer and inner loops.
• Inner variable resets to its initialization value at the start of each outer iteration.
• Preview: 2D array traversal in Unit 4 uses outer loop for rows, inner loop for columns.

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

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

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

int sum = 0;
for (int i = 1; i <= 3; i++) {
    for (int j = 1; j <= 3; j++) {
        sum += i * j;
    }
}

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

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

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

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

int total = 0;
for (int i = 1; i <= 4; i++) {
    for (int j = 1; j <= 4; j++) {
        if (i == j) total += i;
    }
}
System.out.println(total);

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

int[][] result = new int[3][3];
for (int r = 0; r < 3; r++) {
    for (int c = 0; c < 3; c++) {
        result[r][c] = r * 3 + c;
    }
}