Nested for loop in Java - Time & Space Complexity

Time Complexity: Nested for loop

O(n²)

Understanding Time Complexity

When we use nested loops, the time it takes to run the code can grow quickly as the input gets bigger.

We want to understand how the running time changes when we add more items to process.

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++) {
        System.out.println(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 loop's print statement runs repeatedly.
• 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 n grows, the total number of print operations grows 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 increases, the operations increase by the square of n, so doubling n makes operations about four times more.

Final Time Complexity

Time Complexity: O(n²)

This means the running time grows very quickly as the input size grows because each item pairs with every other item.

Common Mistake

[X] Wrong: "The nested loops only add up to O(n) because they just run one after another."

[OK] Correct: The loops are inside each other, so the inner loop runs completely for each outer loop step, multiplying the work, not just adding.

Interview Connect

Understanding nested loops helps you explain how your code handles bigger inputs and shows you can think about efficiency clearly.

Self-Check

"What if the inner loop ran only up to a fixed number instead of n? How would the time complexity change?"