Memory efficiency with generators in PHP - Time & Space Complexity

Time Complexity: Memory efficiency with generators

O(n)

Understanding Time Complexity

We want to see how using generators affects the time it takes to run code that processes many items.

How does the program's work grow when we use generators instead of regular arrays?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function numbersGenerator($n) {
    for ($i = 0; $i < $n; $i++) {
        yield $i;
    }
}

foreach (numbersGenerator(1000) as $num) {
    // process $num
}
    

This code generates numbers from 0 to n-1 one by one without storing them all at once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop runs from 0 to n-1 yielding one number each time.
• How many times: Exactly n times, once per number generated.

How Execution Grows With Input

Each number is generated and processed one at a time, so work grows directly with n.

Input Size (n)	Approx. Operations
10	10 operations
100	100 operations
1000	1000 operations

Pattern observation: The work grows in a straight line as n increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the code grows directly in proportion to the number of items generated.

Common Mistake

[X] Wrong: "Using generators makes the code run faster because it uses less memory."

[OK] Correct: Generators save memory but do not reduce the number of steps the program takes to process each item.

Interview Connect

Understanding how generators affect time helps you explain efficient data processing in real projects.

Self-Check

"What if we replaced the generator with an array that holds all numbers at once? How would the time complexity change?"