Nested loop execution in PHP - Time & Space Complexity

Time Complexity: Nested loop execution

O(n^2)

Understanding Time Complexity

When we have loops inside loops, the time it takes to run the code can grow quickly.

We want to see how the work increases as the input gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for ($i = 0; $i < $n; $i++) {
    for ($j = 0; $j < $n; $j++) {
        echo $i * $j . "\n";
    }
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop's echo statement runs.
• How many times: The inner loop runs n times for each of the n outer loop runs, so n x n times.

How Execution Grows With Input

As n grows, the total number of times the echo runs grows much faster.

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.

Final Time Complexity

Time Complexity: O(n2)

This means the work grows with the square of the input size, so doubling n 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 outer loop step, multiplying the work, not just adding.

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 up to a fixed number instead of n? How would the time complexity change?"

Practice

1. What happens when a nested loop runs in PHP?
for ($i = 0; $i < 2; $i++) {
for ($j = 0; $j < 3; $j++) {
// code
}
}

easy

A. The inner loop runs completely for each iteration of the outer loop.

B. The outer loop runs completely for each iteration of the inner loop.

C. Both loops run only once.

D. The loops run simultaneously without nesting.

Solution

1. Step 1: Understand loop nesting order

   The outer loop runs from 0 to 1 (2 times). For each outer loop iteration, the inner loop runs fully.

2. Step 2: Inner loop completes all cycles per outer iteration

   For each $i, $j runs from 0 to 2 (3 times), completing all inner cycles before next outer iteration.

3. Final Answer:

   The inner loop runs completely for each iteration of the outer loop. -> Option A

4. Quick Check:

   Inner loop finishes fully inside outer loop [OK]

Hint: Inner loop runs fully inside each outer loop cycle [OK]

Common Mistakes:

• Thinking outer loop runs inside inner loop
• Assuming loops run only once
• Confusing simultaneous execution

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

easy

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

B. for ($i = 0; $i < 2; $i++) { for ($j = 0; $j < 3; $j++) { echo $i . $j; } }

C. for ($i = 0; $i < 2; $i++) for ($j = 0; $j < 3; $j++) echo $i . $j;

D. for $i = 0; $i < 2; $i++ { for $j = 0; $j < 3; $j++ { echo $i . $j; } }

Solution

1. Step 1: Check PHP for loop syntax

   PHP requires parentheses around loop conditions and braces for blocks.

2. Step 2: Validate nested loop syntax

   for ($i = 0; $i < 2; $i++) { for ($j = 0; $j < 3; $j++) { echo $i . $j; } } uses correct parentheses and braces for both loops and echo statement inside.

3. Final Answer:

   for ($i = 0; $i < 2; $i++) { for ($j = 0; $j < 3; $j++) { echo $i . $j; } } -> Option B

4. Quick Check:

   Correct parentheses and braces in nested loops [OK]

Hint: Use parentheses and braces properly in PHP loops [OK]

Common Mistakes:

• Omitting parentheses around loop conditions
• Missing braces for loop blocks
• Incorrect for loop syntax without $ sign

3. What is the output of this PHP code?

for ($i = 1; $i <= 2; $i++) {
  for ($j = 1; $j <= 3; $j++) {
    echo $i * $j . ' ';
  }
}

medium

A. 1 2 3 1 2 3

B. 1 4 9 2 5 8

C. 1 2 3 2 4 6

D. 6 12 18 6 12 18

Solution

1. Step 1: Trace outer loop values

   $i runs from 1 to 2.

2. Step 2: Trace inner loop and calculate products

   For $i=1: $j=1,2,3 -> 1*1=1, 1*2=2, 1*3=3
   For $i=2: $j=1,2,3 -> 2*1=2, 2*2=4, 2*3=6

3. Final Answer:

   1 2 3 2 4 6 -> Option C

4. Quick Check:

   Multiply outer and inner loop counters [OK]

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

Common Mistakes:

• Mixing up loop variable values
• Printing inner loop values only
• Ignoring multiplication in echo

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

for ($i = 0; $i < 3; $i++) {
  for ($j = 0; $j < 2; $i++) {
    echo $i . $j . ' ';
  }
}

medium

A. Inner loop increments $i instead of $j causing infinite loop.

B. Outer loop condition is incorrect.

C. Missing semicolon after echo statement.

D. Variables $i and $j are not declared.

Solution

1. Step 1: Check inner loop increment variable

   The inner loop increments $i instead of $j, which is wrong.

2. Step 2: Understand effect of wrong increment

   Incrementing $i inside inner loop changes outer loop variable unexpectedly, causing infinite or wrong behavior.

3. Final Answer:

   Inner loop increments $i instead of $j causing infinite loop. -> Option A

4. Quick Check:

   Increment correct loop variable to avoid errors [OK]

Hint: Increment inner loop variable inside inner loop [OK]

Common Mistakes:

• Incrementing wrong variable in inner loop
• Confusing loop conditions
• Assuming variables need declaration in PHP

5. You want to print a multiplication table from 1 to 3 using nested loops in PHP. Which code correctly prints the table with each row on a new line?

?

hard

A. for ($i = 1; $i <= 3; $i++) { for ($j = 1; $j <= 3; $j++) { echo $i * $j; } echo "\n"; }

B. for ($i = 1; $i <= 3; $i++) { for ($j = 1; $j <= 3; $j++) { echo $i * $j . "\n"; } }

C. for ($i = 1; $i <= 3; $i++) { for ($j = 1; $j <= 3; $j++) { echo $i * $j . ' '; } }

D. for ($i = 1; $i <= 3; $i++) { for ($j = 1; $j <= 3; $j++) { echo $i * $j . ' '; } echo "\n"; }

Solution

1. Step 1: Understand output format

   Each row should print products separated by spaces, then a newline after inner loop ends.

2. Step 2: Check each option for correct newline placement

   for ($i = 1; $i <= 3; $i++) { for ($j = 1; $j <= 3; $j++) { echo $i * $j . ' '; } echo "\n"; } prints products with spaces inside inner loop, then newline after inner loop completes, correctly formatting rows.

3. Final Answer:

   for ($i = 1; $i <= 3; $i++) { for ($j = 1; $j <= 3; $j++) { echo $i * $j . ' '; } echo "\n"; } -> Option D

4. Quick Check:

   Newline after inner loop completes for each row [OK]

Hint: Print newline after inner loop to separate rows [OK]

Common Mistakes:

• Printing newline inside inner loop
• Missing spaces between numbers
• No newline causing all output in one line