Nested loops in Javascript - 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.

function printPairs(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      console.log(arr[i], arr[j]);
    }
  }
}
    

This code prints every possible pair of elements from the array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

As the array gets bigger, the number of pairs grows much faster.

Input Size (n)	Approx. Operations
10	100
100	10,000
1000	1,000,000

Pattern observation: When the input size doubles, the work grows by about four times.

Final Time Complexity

Time Complexity: O(n²)

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

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 step of the outer loop, multiplying the work, not just adding.

Interview Connect

Understanding nested loops helps you explain how your code scales and shows you can spot when code might get slow with big inputs.

Self-Check

"What if the inner loop only ran up to i instead of the full array length? How would the time complexity change?"

Practice

1. What does a nested loop in JavaScript mean?
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 2; j++) {
console.log(i, j);
}
}

easy

A. A loop inside another loop, running multiple times

B. A loop that runs only once

C. A loop that runs backwards

D. A loop that skips some numbers

Solution

1. Step 1: Understand the code structure

   The code has one loop inside another, called nested loops.

2. Step 2: Explain the behavior

   The inner loop runs fully for each iteration of the outer loop, so it runs multiple times.

3. Final Answer:

   A loop inside another loop, running multiple times -> Option A

4. Quick Check:

   Nested loop = loop inside loop [OK]

Hint: Nested means one loop inside another [OK]

Common Mistakes:

• Thinking nested loops run only once
• Confusing nested loops with single loops
• Believing nested loops skip numbers

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

easy

A. for (let i = 0; i < 3; i++) { for (let j = 0; j < 2; j++) { } }

B. for i in range(3) { for j in range(2) { } }

C. while (i < 3) { while (j < 2) }

D. loop i from 0 to 3 { loop j from 0 to 2 { } }

Solution

1. Step 1: Identify JavaScript loop syntax

   JavaScript uses for (let variable = start; condition; increment) syntax.

2. Step 2: Check nested loops syntax

   for (let i = 0; i < 3; i++) { for (let j = 0; j < 2; j++) { } } correctly nests two for loops with proper syntax and braces.

3. Final Answer:

   for (let i = 0; i < 3; i++) { for (let j = 0; j < 2; j++) { } } -> Option A

4. Quick Check:

   JS nested loops use for(;;) inside for(;;) [OK]

Hint: Look for 'for (let i=0; ...)' syntax in JavaScript [OK]

Common Mistakes:

• Using Python or other language syntax
• Missing curly braces {}
• Incorrect loop keywords

3. What is the output of this code?

for (let i = 1; i <= 2; i++) {
  for (let j = 1; j <= 3; j++) {
    console.log(i * j);
  }
}

medium

A. 1 2 3 1 2 3

B. 6 5 4 3 2 1

C. 1 4 9 2 5 8

D. 1 2 3 2 4 6

Solution

1. Step 1: Trace outer loop values

   Outer loop i runs 1 and 2.

2. Step 2: Calculate inner loop outputs

   For i=1, j=1,2,3 outputs 1*1=1, 1*2=2, 1*3=3.
   For i=2, j=1,2,3 outputs 2*1=2, 2*2=4, 2*3=6.

3. Final Answer:

   1 2 3 2 4 6 -> Option D

4. Quick Check:

   Multiply i and j in nested loops [OK]

Hint: Multiply outer and inner loop counters [OK]

Common Mistakes:

• Mixing up i and j values
• Not running inner loop fully each time
• Confusing output order

4. Find the error in this nested loop code:

for (let i = 0; i < 3; i++) {
  for (let i = 0; i < 2; i++) {
    console.log(i);
  }
}

medium

A. Outer loop condition is wrong

B. Missing semicolon after for loops

C. Inner loop uses same variable name 'i', causing conflict

D. Console.log syntax is incorrect

Solution

1. Step 1: Check variable names in loops

   Both loops use variable 'i', inner loop redeclares 'i' shadowing outer.

2. Step 2: Explain why this is a problem

   Using same variable name causes confusion and unexpected behavior in nested loops.

3. Final Answer:

   Inner loop uses same variable name 'i', causing conflict -> Option C

4. Quick Check:

   Use different variables for nested loops [OK]

Hint: Use different variable names for each loop [OK]

Common Mistakes:

• Reusing same variable name in nested loops
• Ignoring variable scope issues
• Assuming semicolons are mandatory after for()

5. You want to print a 3x3 grid of stars (*) using nested loops. Which code correctly does this?

hard

A. for (let i = 0; i < 3; i++) { for (let j = 0; j < 3; j++) { console.log('*'); } }

B. for (let i = 0; i < 3; i++) { let row = ''; for (let j = 0; j < 3; j++) { row += '*'; } console.log(row); }

C. for (let i = 0; i < 3; i++) { console.log('***'); }

D. for (let i = 0; i < 3; i++) { let row = '*'; for (let j = 0; j < 3; j++) { row += '*'; } console.log(row); }

Solution

1. Step 1: Understand the goal

   We want 3 rows, each with 3 stars printed together as a line.

2. Step 2: Check each option's output

   for (let i = 0; i < 3; i++) { let row = ''; for (let j = 0; j < 3; j++) { row += '*'; } console.log(row); } builds a string of 3 stars per row and prints it 3 times.
   for (let i = 0; i < 3; i++) { for (let j = 0; j < 3; j++) { console.log('*'); } } prints stars individually, not as rows.
   for (let i = 0; i < 3; i++) { console.log('***'); } prints 3 stars but only 3 times, no loop for columns.
   for (let i = 0; i < 3; i++) { let row = '*'; for (let j = 0; j < 3; j++) { row += '*'; } console.log(row); } starts with '*' and adds three more '*', printing four stars per row.

3. Final Answer:

   for (let i = 0; i < 3; i++) { let row = ''; for (let j = 0; j < 3; j++) { row += '*'; } console.log(row); } -> Option B

4. Quick Check:

   Build row string inside outer loop [OK]

Hint: Build each row string inside outer loop [OK]

Common Mistakes:

• Printing stars one by one without grouping
• Not resetting row string inside outer loop
• Confusing loops for rows and columns