Fibers for concurrency in PHP - Time & Space Complexity

Time Complexity: Fibers for concurrency

O(n * m)

Understanding Time Complexity

When using fibers for concurrency in PHP, it's important to understand how the program's running time changes as tasks increase.

We want to see how the number of tasks affects the total execution time when fibers switch between them.

Scenario Under Consideration

Analyze the time complexity of the following PHP code using fibers.

$fiber1 = new Fiber(function() {
    for ($i = 0; $i < 5; $i++) {
        echo "Fiber 1: $i\n";
        Fiber::suspend();
    }
});

$fiber2 = new Fiber(function() {
    for ($i = 0; $i < 5; $i++) {
        echo "Fiber 2: $i\n";
        Fiber::suspend();
    }
});

$fiber1->start();
$fiber2->start();

while (!$fiber1->isTerminated() || !$fiber2->isTerminated()) {
    if (!$fiber1->isTerminated()) $fiber1->resume();
    if (!$fiber2->isTerminated()) $fiber2->resume();
}
    

This code runs two fibers that each print numbers 0 to 4, switching between them after each print.

Identify Repeating Operations

Look at what repeats in this code:

• Primary operation: Each fiber runs a loop 5 times, printing and suspending.
• How many times: Each fiber resumes 5 times, so total 10 resumes combined.

How Execution Grows With Input

Imagine increasing the number of fibers or loop counts:

Input Size (n)	Approx. Operations
10 (fibers or loop count)	About 10 x 5 = 50 resumes
100	About 100 x 5 = 500 resumes
1000	About 1000 x 5 = 5000 resumes

Pattern observation: The total steps grow roughly linearly with the input if only one of fibers or loop counts increases.

Final Time Complexity

Time Complexity: O(n * m)

This means the total work grows by multiplying the number of fibers (n) and the number of steps each fiber runs (m).

Common Mistake

[X] Wrong: "Fibers run all tasks at the same time, so time stays the same no matter how many tasks there are."

[OK] Correct: Fibers switch tasks but still run each step one after another, so total time adds up with more tasks.

Interview Connect

Understanding how fibers affect time helps you explain concurrency clearly and shows you know how programs handle multiple tasks efficiently.

Self-Check

"What if we changed the code to run fibers in parallel without suspending? How would the time complexity change?"