Nested for loop in Java - Time & Space Complexity

Time Complexity: Nested for loop

O(n²)

Understanding Time Complexity

When we use nested loops, the time it takes to run the code can grow quickly as the input gets bigger.

We want to understand how the running time changes when we add more items to process.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code prints pairs of numbers where both loops run from 0 to n-1.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop's print statement runs repeatedly.
• How many times: The outer loop runs n times, and for each outer loop, the inner loop runs n times, so total n x n = n² times.

How Execution Grows With Input

As n grows, the total number of print operations grows much faster because of the two loops inside each other.

Input Size (n)	Approx. Operations
10	100
100	10,000
1000	1,000,000

Pattern observation: When n increases, the operations increase by the square of n, so doubling n makes operations about four times more.

Final Time Complexity

Time Complexity: O(n²)

This means the running time grows very quickly as the input size grows because each item pairs with every other item.

Common Mistake

[X] Wrong: "The nested loops only add up to O(n) because they just run one after another."

[OK] Correct: The loops are inside each other, so the inner loop runs completely for each outer loop step, multiplying the work, not just adding.

Interview Connect

Understanding nested loops helps you explain how your code handles bigger inputs and shows you can think about efficiency clearly.

Self-Check

"What if the inner loop ran only up to a fixed number instead of n? How would the time complexity change?"

Practice

1. What does a nested for loop in Java do?
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 2; j++) {
// code
}
}

easy

A. Runs one loop inside another to repeat code multiple times

B. Runs two loops one after another sequentially

C. Runs only the inner loop multiple times

D. Runs only the outer loop once

Solution

1. Step 1: Analyze nested loop iterations

   The outer loop runs 3 times, and for each outer loop iteration, the inner loop runs 2 times.

2. Step 2: Explain the repetition behavior

   This means the inner loop runs fully inside each outer loop iteration, repeating code multiple times in total.

3. Final Answer:

   Runs one loop inside another to repeat code multiple times -> Option A

4. Quick Check:

   Nested loops = inner loop inside outer loop [OK]

Hint: Nested loops repeat inner loop fully for each outer loop [OK]

Common Mistakes:

• Thinking loops run sequentially, not nested
• Confusing inner and outer loop counts
• Assuming only one loop runs multiple times

2. Which of the following is the correct syntax for a nested for loop in Java?

easy

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

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

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

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

Solution

1. Step 1: Verify Java for loop syntax requirements

   Java for loops require parentheses around initialization, condition, and increment, and braces for blocks.

2. Step 2: Identify correct nested loop syntax

   for (int i = 0; i < 3; i++) { for (int j = 0; j < 2; j++) System.out.println(i + j); } correctly uses braces for outer loop without extra invalid keywords or else blocks.

3. Final Answer:

   for (int i = 0; i < 3; i++) { for (int j = 0; j < 2; j++) System.out.println(i + j); } -> Option A

4. Quick Check:

   Correct Java syntax = for (int i = 0; i < 3; i++) { for (int j = 0; j < 2; j++) System.out.println(i + j); } [OK]

Hint: Remember Java for loop needs parentheses and braces [OK]

Common Mistakes:

• Missing parentheses around for loop conditions
• Using else after for loop incorrectly
• Omitting braces for multiple statements

3. What is the output of this Java code?

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

medium

A. 2 4 6
4 8 12

B. 1 2 3 4 5 6

C. 1 2 3
1 2 3

D. 1 2 3
2 4 6

Solution

1. Step 1: Trace outer loop iterations

   Outer loop runs i=1 and i=2.

2. Step 2: Calculate inner loop outputs for each i

   For i=1: j=1,2,3 outputs 1*1=1, 1*2=2, 1*3=3.
   For i=2: j=1,2,3 outputs 2*1=2, 2*2=4, 2*3=6.

3. Final Answer:

   1 2 3 2 4 6 -> Option D

4. Quick Check:

   Multiply i and j in nested loops = 1 2 3 2 4 6 [OK]

Hint: Multiply outer and inner loop variables for output [OK]

Common Mistakes:

• Ignoring new line after inner loop
• Concatenating all numbers in one line
• Mixing up i and j values

4. Find the error in this nested for loop code:

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

medium

A. Missing semicolon after inner loop

B. Inner loop condition should be j <= 3

C. Extra closing brace '}' after inner loop

D. Outer loop variable i is not initialized

Solution

1. Step 1: Check braces matching

   The inner loop lacks braces but has an extra closing brace '}' after it, causing syntax error.

2. Step 2: Identify correct brace placement

   Remove the extra '}' after inner loop or add braces properly to fix syntax.

3. Final Answer:

   Extra closing brace '}' after inner loop -> Option C

4. Quick Check:

   Brace mismatch error = Extra closing brace '}' after inner loop [OK]

Hint: Match opening and closing braces carefully [OK]

Common Mistakes:

• Adding extra braces after loops
• Omitting braces for multiple statements
• Incorrect loop conditions

5. How can you use nested for loops to print a 4x4 multiplication table in Java?

hard

A. Use a single loop from 1 to 16 and print i * i

B. Use outer loop for rows 1 to 4 and inner loop for columns 1 to 4, print product

C. Use nested loops but print only the outer loop variable

D. Use nested loops but skip printing inside inner loop

Solution

1. Step 1: Set outer loop for rows 1 to 4

   The outer loop controls the row number from 1 to 4.

2. Step 2: Set inner loop for columns 1 to 4 and print product

   The inner loop runs columns 1 to 4, printing the product of row and column numbers to form the table.

3. Final Answer:

   Use outer loop for rows 1 to 4 and inner loop for columns 1 to 4, print product -> Option B

4. Quick Check:

   Nested loops for rows and columns = Use outer loop for rows 1 to 4 and inner loop for columns 1 to 4, print product [OK]

Hint: Outer loop rows, inner loop columns, print product [OK]

Common Mistakes:

• Using single loop for 2D table
• Not printing product of both loop variables
• Skipping inner loop printing