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