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