Nested loops in C - Time & Space Complexity

Time Complexity: Nested loops

O(n²)

Understanding Time Complexity

When we use loops inside other loops, the time it takes to run the code can grow quickly.

We want to understand how the total work changes as the input size grows.

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++) {
        // some constant time operation
        printf("%d %d\n", i, j);
    }
}
    

This code prints pairs of numbers, looping over all combinations 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 many times.
• How many times: The outer loop runs n times, and for each, the inner loop runs n times, so total runs are n x n.

How Execution Grows With Input

As n grows, the total operations grow 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 doubles, the work grows by about four times, showing a square growth.

Final Time Complexity

Time Complexity: O(n²)

This means the work grows roughly with the square of the input size, so bigger inputs take much more time.

Common Mistake

[X] Wrong: "Since there are two loops, the time is just twice as long as one loop."

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

Interview Connect

Understanding nested loops helps you explain how your code scales and shows you can spot when things might get slow with bigger inputs.

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 loop in C do?
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 2; j++) {
// code
}
}

easy

A. Runs one loop inside another, repeating inner loop fully each outer loop

B. Runs two loops side by side without interaction

C. Runs only the outer loop multiple times

D. Runs only the inner loop once

Solution

1. Step 1: Understand nested loops structure

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

2. Step 2: Explain the repetition

   Each time the outer loop runs once, the inner loop runs completely, repeating the inner code multiple times.

3. Final Answer:

   Runs one loop inside another, repeating inner loop fully each outer loop -> Option A

4. Quick Check:

   Nested loops repeat inner loop per outer loop [OK]

Hint: Inner loop runs fully for each outer loop iteration [OK]

Common Mistakes:

• Thinking loops run side by side without nesting
• Assuming inner loop runs only once
• Confusing outer and inner loop roles

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

easy

A. for int i = 0; i < 3; i++ { for int j = 0; j < 2; j++ { /* code */ } }

B. for (int i = 0; i < 3; i++) { for (int j = 0; j < 2; j++) /* code */ }

C. for (int i = 0; i < 3; i++) for (int j = 0; j < 2; j++) { /* code */ }

D. for (int i = 0; i < 3; i++) { for (int j = 0; j < 2; j++) { /* code */ }

Solution

1. Step 1: Check syntax correctness

   for (int i = 0; i < 3; i++) for (int j = 0; j < 2; j++) { /* code */ } uses correct C syntax with parentheses and braces properly placed.

2. Step 2: Identify syntax errors in other options

   for int i = 0; i < 3; i++ { for int j = 0; j < 2; j++ { /* code */ } } misses parentheses and braces; for (int i = 0; i < 3; i++) { for (int j = 0; j < 2; j++) /* code */ } misses braces for inner loop; for (int i = 0; i < 3; i++) { for (int j = 0; j < 2; j++) { /* code */ } misses closing brace for outer loop.

3. Final Answer:

   for (int i = 0; i < 3; i++) for (int j = 0; j < 2; j++) { /* code */ } -> Option C

4. Quick Check:

   Correct for loop syntax uses parentheses and braces [OK]

Hint: Remember for loops need parentheses and braces [OK]

Common Mistakes:

• Omitting parentheses around loop conditions
• Missing braces for loop bodies
• Incorrect variable declaration syntax

3. What is the output of this C code?

for (int i = 1; i <= 2; i++) {
  for (int j = 1; j <= 3; j++) {
    printf("%d%d ", i, j);
  }
}

medium

A. 12 13 21 23

B. 11 12 13 21 22 23

C. 123 123

D. 11 21 12 22 13 23

Solution

1. Step 1: Trace outer loop iterations

   Outer loop runs i=1 and i=2.

2. Step 2: Trace inner loop for each outer iteration

   For i=1, inner loop prints 11 12 13; for i=2, inner loop prints 21 22 23.

3. Final Answer:

   11 12 13 21 22 23 -> Option B

4. Quick Check:

   Nested loops print pairs in order [OK]

Hint: Outer loop controls first digit, inner loop second digit [OK]

Common Mistakes:

• Mixing order of printed pairs
• Printing numbers without spaces
• Confusing loop limits

4. Find the error in this nested loop code:

for (int i = 0; i < 3; i++) {
  for (int j = 0; j < 3; j++)
    printf("%d%d\n", i, j);
  }
}

medium

A. Extra closing brace '}' after inner loop

B. Missing semicolon after printf

C. Inner loop missing braces causing syntax error

D. Outer loop condition is incorrect

Solution

1. Step 1: Check braces matching

   There is an extra closing brace after the inner loop which causes a syntax error.

2. Step 2: Verify other syntax parts

   Printf has semicolon; inner loop without braces is allowed for single statement; outer loop condition is correct.

3. Final Answer:

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

4. Quick Check:

   Braces must match exactly [OK]

Hint: Count opening and closing braces carefully [OK]

Common Mistakes:

• Adding extra braces accidentally
• Assuming missing braces always cause error
• Ignoring semicolon after statements

5. How many times will the innermost statement run in this nested loop?

for (int i = 1; i <= 4; i++) {
  for (int j = i; j <= 4; j++) {
    for (int k = 1; k <= j; k++) {
      printf("*");
    }
  }
}

hard

A. 70

B. 50

C. 40

D. 30

Solution

1. Step 1: Analyze loop ranges

   i runs 1 to 4; for each i, j runs from i to 4; for each j, k runs 1 to j.

2. Step 2: Calculate total iterations

   Calculate sum over i=1 to 4 of sum over j=i to 4 of j:
   i=1: j=1..4 sum=1+2+3+4=10
   i=2: j=2..4 sum=2+3+4=9
   i=3: j=3..4 sum=3+4=7
   i=4: j=4..4 sum=4
   Total = 10+9+7+4=30

3. Final Answer:

   30 -> Option D

4. Quick Check:

   Total iterations = 10+9+7+4=30 [OK]

Hint: Sum inner loop counts carefully per outer loops [OK]

Common Mistakes:

• Adding loop counts incorrectly
• Ignoring changing start of inner loops
• Confusing loop variables