Nested while loops in Python - Time & Space Complexity

Time Complexity: Nested while loops

O(n²)

Understanding Time Complexity

When we use nested while loops, the program runs some steps inside other steps repeatedly.

We want to know how the total work grows as the input gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

i = 0
while i < n:
    j = 0
    while j < n:
        print(i, j)
        j += 1
    i += 1

This code prints pairs of numbers from 0 up to n-1 using two loops inside each other.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner while loop that prints pairs.
• How many times: The inner loop runs n times for each of the n times the outer loop runs.

How Execution Grows With Input

As n grows, the total prints grow much faster because each outer step triggers many inner steps.

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

Pattern observation: The work grows by the square of n, so doubling n makes the work about four times bigger.

Final Time Complexity

Time Complexity: O(n²)

This means if the input doubles, the total steps roughly become four times more.

Common Mistake

[X] Wrong: "The nested loops just add their times, so it is O(n + n) = O(n)."

[OK] Correct: The inner loop runs completely for each outer loop step, so the total work multiplies, not adds.

Interview Connect

Understanding nested loops helps you explain how programs handle repeated tasks inside other repeated tasks, a common pattern in coding challenges.

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 while loop do in Python?
while condition1:
  while condition2:
    # code

easy

A. Runs the inner loop completely for each iteration of the outer loop

B. Runs both loops only once

C. Runs the outer loop only after the inner loop finishes all iterations

D. Runs the inner loop only if the outer loop condition is false

Solution

1. Step 1: Understand nested loops structure

   The outer loop runs while condition1 is true. For each iteration of this outer loop, the inner loop runs fully while condition2 is true.

2. Step 2: Explain the inner loop behavior

   The inner loop completes all its iterations before the outer loop moves to the next iteration.

3. Final Answer:

   Runs the inner loop completely for each iteration of the outer loop -> Option A

4. Quick Check:

   Inner loop runs fully inside outer loop [OK]

Hint: Inner loop finishes all cycles before outer loop continues [OK]

Common Mistakes:

• Thinking both loops run only once
• Confusing order of loop execution
• Assuming inner loop runs only if outer loop is false

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

easy

A. while x < 3:
while y < 2:
print(x, y)
y += 1

B. while x < 3
while y < 2:
print(x, y)
y += 1

C. while x < 3:
while y < 2:
print(x, y)
y += 1

D. while x < 3:
while y < 2:
print(x, y)
y += 1

Solution

1. Step 1: Check indentation and colons

   Python requires a colon after while conditions and proper indentation for nested blocks.

2. Step 2: Identify correct indentation and syntax

   while x < 3: while y < 2: print(x, y) y += 1 uses colons and indents the inner while and print statements correctly.

3. Final Answer:

   while x < 3: while y < 2: print(x, y) y += 1 -> Option D

4. Quick Check:

   Correct colons and indentation = while x < 3: while y < 2: print(x, y) y += 1 [OK]

Hint: Look for colons and consistent indentation [OK]

Common Mistakes:

• Missing colons after while statements
• Incorrect indentation of inner loop
• Mixing indentation levels

3. What is the output of this code?

i = 1
while i <= 2:
    j = 1
    while j <= 3:
        print(i, j)
        j += 1
    i += 1

medium

A. 1 1\n1 2\n2 1\n2 2

B. 1 1\n2 1\n3 1

C. 1 1\n1 2\n1 3\n2 1\n2 2\n2 3

D. 1 1\n1 2\n1 3

Solution

1. Step 1: Trace outer loop iterations

   i starts at 1 and runs while i <= 2, so i = 1 and i = 2.

2. Step 2: Trace inner loop iterations for each i

   For each i, j runs from 1 to 3, printing i and j each time.

3. Final Answer:

   1 1\n1 2\n1 3\n2 1\n2 2\n2 3 -> Option C

4. Quick Check:

   Inner loop prints 3 times per outer loop iteration [OK]

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

Common Mistakes:

• Only printing inner loop once
• Mixing up i and j values
• Stopping loops too early

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

i = 0
while i < 2:
    j = 0
    while j < 2:
    print(i, j)
    j += 1
    i += 1

medium

A. No error, code runs fine

B. Inner loop print and increments are not indented properly

C. Variables i and j are not initialized

D. Outer loop condition is incorrect

Solution

1. Step 1: Check indentation inside inner while loop

   The print and j increment lines must be indented inside the inner while loop to run repeatedly.

2. Step 2: Identify effect of wrong indentation

   Without indentation, print and j += 1 run only once, causing an infinite loop or logic error.

3. Final Answer:

   Inner loop print and increments are not indented properly -> Option B

4. Quick Check:

   Indent inner loop body correctly [OK]

Hint: Indent inner loop body to avoid logic errors [OK]

Common Mistakes:

• Forgetting to indent inner loop code
• Incrementing outer loop variable inside inner loop
• Misplacing loop conditions

5. You want to print a 3x3 grid of numbers where each cell shows the sum of its row and column indexes (starting from 1). Which nested while loop code correctly does this?

hard

A. row = 1
while row <= 3:
col = 1
while col <= 3:
print(row + col, end=' ')
col += 1
print()
row += 1

B. row = 1
while row <= 3:
col = 1
while col <= 3:
print(row * col, end=' ')
col += 1
print()
row += 1

C. row = 0
while row < 3:
col = 0
while col < 3:
print(row + col, end=' ')
col += 1
print()
row += 1

D. row = 1
while row < 3:
col = 1
while col < 3:
print(row + col, end=' ')
col += 1
print()
row += 1

Solution

1. Step 1: Check loop ranges for 1 to 3

   We want rows and columns from 1 to 3 inclusive, so conditions should be <= 3 starting at 1.

2. Step 2: Verify sum calculation and printing format

   row = 1 while row <= 3: col = 1 while col <= 3: print(row + col, end=' ') col += 1 print() row += 1 sums row and col indexes and prints with space, then prints a newline after each row.

3. Final Answer:

   row = 1 while row <= 3: col = 1 while col <= 3: print(row + col, end=' ') col += 1 print() row += 1 -> Option A

4. Quick Check:

   Correct ranges and sum print = row = 1 while row <= 3: col = 1 while col <= 3: print(row + col, end=' ') col += 1 print() row += 1 [OK]

Hint: Use <= 3 and start from 1 for correct grid indexes [OK]

Common Mistakes:

• Starting loops at 0 instead of 1
• Using < 3 instead of <= 3 to miss last row/column
• Printing product instead of sum