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 gets bigger.

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
        std::cout << i * j << std::endl;
    }
}
    

This code prints the product of i and j for every pair of numbers from 0 to n-1.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop runs a print operation.
• How many times: The inner loop runs n times for each of the n iterations of the outer loop, so n x n times total.

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 gets 10 times bigger, the work gets 100 times bigger because of the nested loops.

Final Time Complexity

Time Complexity: O(n²)

This means the work grows by the square of the input size, so doubling n makes the work about four times bigger.

Common Mistake

[X] Wrong: "The time grows just a little bit because the loops are simple."

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

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 half as many times as the outer loop? How would the time complexity change?"