Generator function execution model in PHP - Time & Space Complexity

Time Complexity: Generator function execution model

O(n)

Understanding Time Complexity

We want to understand how the time cost changes when using a generator function in PHP.

Specifically, how does the generator's execution grow as it yields values?

Scenario Under Consideration

Analyze the time complexity of the following generator function.

function countToN(int $n) {
    for ($i = 1; $i <= $n; $i++) {
        yield $i;
    }
}

$gen = countToN(5);
foreach ($gen as $value) {
    echo $value . "\n";
}

This code yields numbers from 1 to n one by one, pausing after each yield.

Identify Repeating Operations

Look at what repeats during execution.

• Primary operation: The loop runs from 1 to n, yielding each number.
• How many times: Exactly n times, once per number.

How Execution Grows With Input

Each time we ask the generator for the next value, it runs one loop step.

Input Size (n)	Approx. Operations
10	10 loop steps, 10 yields
100	100 loop steps, 100 yields
1000	1000 loop steps, 1000 yields

Pattern observation: The number of steps grows directly with n, one step per yield.

Final Time Complexity

Time Complexity: O(n)

This means the time to get all values grows linearly with how many values we want.

Common Mistake

[X] Wrong: "The generator runs all loop steps at once when created."

[OK] Correct: The generator pauses at each yield, so it only does one step per request, not all at once.

Interview Connect

Understanding how generators pause and resume helps you explain efficient data processing in interviews.

Self-Check

"What if the generator yielded values from a nested loop? How would the time complexity change?"