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?