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?"