Nested loops in Go - Time & Space Complexity

Time Complexity: Nested loops

O(n²)

Understanding Time Complexity

When we use nested loops, the program does some work inside another loop. This means the total work can grow quickly as the input gets bigger.

We want to understand how the time needed changes when the input size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for i := 0; i < n; i++ {
    for j := 0; j < n; j++ {
        // some constant time operation
    }
}
    

This code runs a simple operation inside two loops, one inside the other, both running n times.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop's constant time operation.
• How many times: The inner operation runs once for every pair of i and j, so n times for i and n times for j, total n x n times.

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 operations increase by about four times, showing a square growth.

Final Time Complexity

Time Complexity: O(n²)

This means the time needed grows roughly with the square of the input size, so bigger inputs take much more time.

Common Mistake

[X] Wrong: "The nested loops just add up, so the time is O(n + n) which is O(n)."

[OK] Correct: The loops multiply their work because the inner loop runs completely for each step of the outer loop, so the total work is much larger than just adding.

Interview Connect

Understanding nested loops helps you explain how your code behaves with bigger data. It shows you can think about efficiency, which is a key skill in programming.

Self-Check

"What if the inner loop ran only a fixed number of times, say 10, regardless of n? How would the time complexity change?"