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