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

Practice

1. What does the yield keyword do inside a PHP generator function?

easy

A. It pauses the function and returns a value to the caller.

B. It immediately ends the function and returns a value.

C. It creates a new variable inside the function.

D. It calls another function asynchronously.

Solution

1. Step 1: Understand the role of yield in generators

   The yield keyword pauses the function execution and sends a value back to the caller without ending the function.

2. Step 2: Compare with other options

   Unlike return, yield does not end the function but allows it to resume later.

3. Final Answer:

   It pauses the function and returns a value to the caller. -> Option A

4. Quick Check:

   yield pauses and returns value [OK]

Hint: Remember: yield pauses, return ends function [OK]

Common Mistakes:

• Confusing yield with return
• Thinking yield creates variables
• Assuming yield calls other functions

2. Which of the following is the correct syntax to define a generator function in PHP?

easy

A. function gen() { return yield 1; }

B. function gen() { yield 1; }

C. function gen() => yield 1;

D. generator gen() { yield 1; }

Solution

1. Step 1: Identify correct generator syntax

   In PHP, a generator function is a normal function that uses yield inside its body.

2. Step 2: Check each option

   function gen() { yield 1; } uses a normal function with yield correctly. function gen() { return yield 1; } misuses return yield. function gen() => yield 1; uses invalid arrow syntax. generator gen() { yield 1; } uses an invalid keyword generator.

3. Final Answer:

   function gen() { yield 1; } -> Option B

4. Quick Check:

   Normal function + yield = generator [OK]

Hint: Generator = function with yield inside braces [OK]

Common Mistakes:

• Using return with yield incorrectly
• Trying arrow function syntax for generators
• Using non-existent keywords like 'generator'

3. What will be the output of the following PHP code?

function gen() {
  yield 1;
  yield 2;
  yield 3;
}
foreach (gen() as $value) {
  echo $value . ' ';
}

medium

A. 123

B. Error: Cannot use foreach on generator

C. 1,2,3

D. 1 2 3

Solution

1. Step 1: Understand generator yields

   The generator yields values 1, then 2, then 3 in sequence.

2. Step 2: Analyze foreach output

   The foreach loops over each yielded value and echoes it followed by a space, so output is "1 2 3 "

3. Final Answer:

   1 2 3 -> Option D

4. Quick Check:

   foreach prints each yield with space [OK]

Hint: foreach prints each yield value in order [OK]

Common Mistakes:

• Ignoring spaces in echo output
• Thinking foreach can't iterate generators
• Confusing output format with commas

4. Identify the error in this PHP generator function:

function gen() {
  yield 1;
  return 2;
  yield 3;
}
foreach (gen() as $v) {
  echo $v;
}

medium

A. Syntax error: return not allowed in generator

B. No error, outputs 123

C. The return ends generator early, so yield 3 is never reached

D. foreach cannot iterate generator with return

Solution

1. Step 1: Understand return in generators

   Return ends the generator function immediately, so code after return is not executed.

2. Step 2: Analyze code flow

   After yielding 1, the return 2 ends the generator, so yield 3 is never reached or yielded.

3. Final Answer:

   The return ends generator early, so yield 3 is never reached -> Option C

4. Quick Check:

   Return stops generator, later yields skipped [OK]

Hint: Return ends generator; yields after return ignored [OK]

Common Mistakes:

• Thinking return causes syntax error
• Expecting all yields to run despite return
• Assuming foreach can't handle return in generator

5. Given this generator function, what will be the output?

function gen() {
  for ($i = 0; $i < 3; $i++) {
    yield $i => $i * 2;
  }
}
foreach (gen() as $key => $value) {
  echo "$key:$value ";
}

hard

A. 0:0 1:2 2:4

B. 0:0 1:1 2:2

C. 0 2 4

D. Error: Cannot yield key => value in PHP

Solution

1. Step 1: Understand yield with key => value

   The generator yields keys 0,1,2 with values 0,2,4 respectively (value = key * 2).

2. Step 2: Analyze foreach output

   foreach prints each key and value separated by colon and space, so output is "0:0 1:2 2:4 "

3. Final Answer:

   0:0 1:2 2:4 -> Option A

4. Quick Check:

   Yield key=>value prints key:value pairs [OK]

Hint: Yield key=>value pairs print as key:value [OK]

Common Mistakes:

• Confusing value with key
• Thinking yield key=>value is invalid
• Ignoring spaces in output