Nested for loop execution in Python - Time & Space Complexity

Time Complexity: Nested for loop execution

O(n²)

Understanding Time Complexity

When we use nested loops, the program does some work inside another loop. This can make the program take longer as the input grows.

We want to know how the total work grows when the input size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for i in range(n):
    for j in range(n):
        print(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 print statement inside the nested loops.
• 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 the input size n grows, the total number of print operations grows much faster because of the nested loops.

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

Pattern observation: When n increases by 10 times, the operations increase by 100 times, showing a square growth.

Final Time Complexity

Time Complexity: O(n²)

This means the work grows proportionally to the square of the input size, so doubling n makes the work about four times bigger.

Common Mistake

[X] Wrong: "The nested loops only add up to n + n = 2n operations, so it is still linear."

[OK] Correct: Because the inner loop runs completely for each iteration of the outer loop, the total operations multiply, not add, making it n x n, not 2n.

Interview Connect

Understanding nested loops helps you explain how your code scales and shows you can spot when programs might slow down with bigger inputs. This skill is useful in many coding tasks.

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 do in Python?
for i in range(2):
for j in range(3):
print(i, j)

easy

A. Runs the inner loop fully for each outer loop step

B. Runs both loops only once

C. Runs the outer loop fully for each inner loop step

D. Runs only the outer loop

Solution

1. Step 1: Understand nested loop structure

   The outer loop runs 2 times (i=0,1). For each i, the inner loop runs 3 times (j=0,1,2).

2. Step 2: Observe loop execution order

   For each i, the inner loop completes all its iterations before the outer loop moves to next i.

3. Final Answer:

   Runs the inner loop fully for each outer loop step -> Option A

4. Quick Check:

   Inner loop runs fully per outer loop [OK]

Hint: Inner loop runs completely inside each outer loop step [OK]

Common Mistakes:

• Thinking outer loop runs inside inner loop
• Assuming loops run only once
• Confusing loop order

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

easy

A. for i in range(3): for j in range(2): print(i, j)

B. for i in range(3):
for j in range(2):
print(i, j)

C. for i in range(3):
for j in range(2):
print(i, j)

D. for i in range(3):
for j in range(2):
print(i, j)

Solution

1. Step 1: Check indentation rules

   Python requires consistent indentation to define nested blocks. Inner loop must be indented inside outer loop.

2. Step 2: Identify correct indentation

   for i in range(3): for j in range(2): print(i, j) uses 4 spaces indentation for inner loop and print statement, which is correct.

3. Final Answer:

   for i in range(3):\n for j in range(2):\n print(i, j) -> Option B

4. Quick Check:

   Proper indentation = for i in range(3): for j in range(2): print(i, j) [OK]

Hint: Indent inner loop inside outer loop with spaces [OK]

Common Mistakes:

• Missing indentation for inner loop
• Incorrect indentation for print
• Writing loops on same line without colon

3. What is the output of this code?

for i in range(2):
    for j in range(2):
        print(i + j, end=' ')
    print()

medium

A. 0 1 \n0 1

B. 1 2 \n2 3

C. 0 1 1 2

D. 0 1 \n1 2

Solution

1. Step 1: Calculate inner loop sums for i=0

   j=0: 0+0=0, j=1: 0+1=1 -> prints '0 1 '

2. Step 2: Calculate inner loop sums for i=1

   j=0: 1+0=1, j=1: 1+1=2 -> prints '1 2 '

3. Final Answer:

   0 1 \n1 2 -> Option D

4. Quick Check:

   Sum of i and j per line = 0 1 \n1 2 [OK]

Hint: Add i and j for each inner loop iteration [OK]

Common Mistakes:

• Ignoring print() creates new line
• Adding values incorrectly
• Confusing end=' ' usage

4. Find the error in this nested loop code:

for i in range(3):
for j in range(2):
    print(i, j)

medium

A. print statement should be outside loops

B. Missing colon after inner for loop

C. Inner loop not indented inside outer loop

D. range(2) should be range(3)

Solution

1. Step 1: Check indentation of inner loop

   Inner for loop must be indented inside outer loop to be nested properly.

2. Step 2: Identify correct indentation

   Here, inner loop is at same level as outer loop, causing IndentationError.

3. Final Answer:

   Inner loop not indented inside outer loop -> Option C

4. Quick Check:

   Indent inner loop inside outer loop [OK]

Hint: Indent inner loop under outer loop to fix error [OK]

Common Mistakes:

• Not indenting inner loop
• Misplacing colons
• Wrong range values

5. How many times will the print statement execute in this nested loop?

for i in range(4):
    for j in range(3):
        for k in range(2):
            print(i, j, k)

hard

A. 24

B. 12

C. 36

D. 9

Solution

1. Step 1: Calculate iterations of each loop

   Outer loop: 4 times (i=0..3), middle loop: 3 times (j=0..2), inner loop: 2 times (k=0..1).

2. Step 2: Multiply iterations for total prints

   Total = 4 * 3 * 2 = 24 print executions.

3. Step 3: Re-check options

   36 says 36, but calculation is 24, so correct is 24.

4. Final Answer:

   24 -> Option A

5. Quick Check:

   4*3*2 = 24 prints [OK]

Hint: Multiply all loop ranges for total executions [OK]

Common Mistakes:

• Adding instead of multiplying loop counts
• Counting only outer loops
• Misreading loop ranges