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

Practice

1. What does a nested loop in Go do?
for i := 0; i < 3; i++ {
for j := 0; j < 2; j++ {
// code
}
}

easy

A. Runs one loop inside another to repeat code multiple times

B. Runs two loops one after another without overlap

C. Runs only the inner loop once

D. Creates an infinite loop automatically

Solution

1. Step 1: Understand nested loops structure

   The outer loop runs 3 times, and for each outer loop iteration, the inner loop runs 2 times.

2. Step 2: Explain the repetition effect

   This means the inner code runs 3 * 2 = 6 times, repeating actions multiple times inside another loop.

3. Final Answer:

   Runs one loop inside another to repeat code multiple times -> Option A

4. Quick Check:

   Nested loops repeat code multiple times [OK]

Hint: Nested loops repeat inner code for each outer loop cycle [OK]

Common Mistakes:

• Thinking loops run sequentially without nesting
• Assuming inner loop runs only once
• Believing nested loops cause infinite loops automatically

2. Which of the following is the correct syntax for a nested loop in Go?

easy

A. for i := 0; i < 3; i++; for j := 0; j < 2; j++ { fmt.Println(i, j) }

B. for i := 0; i < 3; i++ { for j < 2 { fmt.Println(i, j); j++ } }

C. for i := 0; i < 3; i++ { for j := 0; j < 2; j++ } fmt.Println(i, j)

D. for i := 0; i < 3; i++ { for j := 0; j < 2; j++ { fmt.Println(i, j) } }

Solution

1. Step 1: Check correct nested loop syntax

   for i := 0; i < 3; i++ { for j := 0; j < 2; j++ { fmt.Println(i, j) } } correctly nests the inner for loop inside the outer loop with braces and increments.

2. Step 2: Identify syntax errors in other options

   for i := 0; i < 3; i++ { for j < 2 { fmt.Println(i, j); j++ } } uses a while-style loop without declaring j, causing an undefined variable error in Go. for i := 0; i < 3; i++; for j := 0; j < 2; j++ { fmt.Println(i, j) } has two for loops separated by a semicolon, which is invalid. for i := 0; i < 3; i++ { for j := 0; j < 2; j++ } fmt.Println(i, j) places the print statement outside the inner loop braces, causing scope issues.

3. Final Answer:

   for i := 0; i < 3; i++ { for j := 0; j < 2; j++ { fmt.Println(i, j) } } -> Option D

4. Quick Check:

   Correct nested loop syntax = for i := 0; i < 3; i++ { for j := 0; j < 2; j++ { fmt.Println(i, j) } } [OK]

Hint: Remember Go uses braces and semicolons inside for loops [OK]

Common Mistakes:

• Using semicolon between two for loops instead of nesting
• Trying while-style loops without proper syntax
• Placing code outside loop braces incorrectly

3. What is the output of this Go program?

package main
import "fmt"
func main() {
  for i := 1; i <= 2; i++ {
    for j := 1; j <= 3; j++ {
      fmt.Print(i * j, " ")
    }
    fmt.Println()
  }
}

medium

A. 2 4 6
1 2 3

B. 1 1 1
2 2 2

C. 1 2 3
2 4 6

D. 1 2 3 4 5 6

Solution

1. Step 1: Analyze outer loop iterations

   The outer loop runs for i = 1 and i = 2.

2. Step 2: Calculate inner loop outputs for each i

   For i=1, inner loop prints 1*1=1, 1*2=2, 1*3=3. For i=2, inner loop prints 2*1=2, 2*2=4, 2*3=6.

3. Final Answer:

   1 2 3 2 4 6 -> Option C

4. Quick Check:

   Multiplying i and j in nested loops = 1 2 3 2 4 6 [OK]

Hint: Multiply outer and inner loop counters for output [OK]

Common Mistakes:

• Confusing loop ranges or order
• Printing all numbers in one line without newline
• Mixing up i and j in multiplication

4. Find the error in this nested loop code snippet:

for i := 0; i < 3; i++ {
  for j := 0; j < 2; j++
    fmt.Println(i, j)
}

medium

A. Missing braces {} for inner loop body

B. Outer loop condition is incorrect

C. Inner loop variable j is not declared

D. fmt.Println cannot be used inside loops

Solution

1. Step 1: Check inner loop syntax

   The inner loop lacks braces {} around its body, which is required for multiple statements or to clearly define the loop block in Go.

2. Step 2: Understand Go syntax rules

   Without braces, only the next statement is considered inside the loop. Here, fmt.Println is intended as the loop body but braces improve clarity and prevent errors.

3. Final Answer:

   Missing braces {} for inner loop body -> Option A

4. Quick Check:

   Braces needed for loop body in Go [OK]

Hint: Always use braces {} for nested loop bodies [OK]

Common Mistakes:

• Assuming braces are optional for loops
• Thinking variable declaration is missing
• Believing fmt.Println can't be inside loops

5. You want to print a multiplication table from 1 to 4 using nested loops in Go. Which code snippet correctly achieves this?

hard

A. for i := 1; i < 4; i++ {
for j := 1; j < 4; j++ {
fmt.Println(i*j)
}
}

B. for i := 1; i <= 4; i++ {
for j := 1; j <= 4; j++ {
fmt.Printf("%d ", i*j)
}
fmt.Println()
}

C. for i := 1; i <= 4; i++ {
for j := 1; j <= 4; j++ {
fmt.Println(i+j)
}
fmt.Println()
}

D. for i := 1; i <= 4; i++ {
for j := 1; j <= 4; j++ {
fmt.Printf("%d ", i+j)
}
fmt.Println()
}

Solution

1. Step 1: Identify correct loop ranges

   To print from 1 to 4, loops must run from 1 to 4 inclusive, so conditions use <= 4.

2. Step 2: Check output format and calculation

   for i := 1; i <= 4; i++ { for j := 1; j <= 4; j++ { fmt.Printf("%d ", i*j) } fmt.Println() } multiplies i and j and prints in one line with spaces, then prints a newline after inner loop, forming a table.

3. Step 3: Compare other options

   for i := 1; i < 4; i++ { for j := 1; j < 4; j++ { fmt.Println(i*j) } } uses < 4, missing 4. Options C and D add i+j instead of multiplication, which is incorrect for multiplication table.

4. Final Answer:

   for i := 1; i <= 4; i++ { for j := 1; j <= 4; j++ { fmt.Printf("%d ", i*j) } fmt.Println() } -> Option B

5. Quick Check:

   Correct ranges and multiplication print = for i := 1; i <= 4; i++ { for j := 1; j <= 4; j++ { fmt.Printf("%d ", i*j) } fmt.Println() } [OK]

Hint: Use <= for inclusive range and multiply counters [OK]

Common Mistakes:

• Using < instead of <= to miss last number
• Adding instead of multiplying counters
• Printing each number on a new line instead of a table