Fiber for cooperative concurrency in Ruby - Time & Space Complexity

Time Complexity: Fiber for cooperative concurrency

O(n)

Understanding Time Complexity

When using Fibers for cooperative concurrency, we want to understand how the program's running time changes as we switch between tasks.

We ask: How does the number of Fiber switches affect the total work done?

Scenario Under Consideration

Analyze the time complexity of the following Ruby code using Fibers.

fiber1 = Fiber.new do
  3.times do |i|
    puts "Fiber1: step #{i}"
    Fiber.yield
  end
end

fiber2 = Fiber.new do
  3.times do |i|
    puts "Fiber2: step #{i}"
    Fiber.yield
  end
end

while fiber1.alive? || fiber2.alive?
  fiber1.resume if fiber1.alive?
  fiber2.resume if fiber2.alive?
end

This code runs two Fibers that take turns running steps, yielding control back and forth.

Identify Repeating Operations

Look for loops and repeated Fiber switches.

• Primary operation: The loop that resumes each Fiber until both finish.
• How many times: Each Fiber runs 3 times, so total of 6 resumes and yields combined.

How Execution Grows With Input

Imagine increasing the number of steps each Fiber runs.

Input Size (steps per Fiber)	Approx. Operations (Fiber resumes)
10	20 (2 Fibers x 10 steps)
100	200 (2 Fibers x 100 steps)
1000	2000 (2 Fibers x 1000 steps)

Pattern observation: The total operations grow linearly with the number of steps per Fiber.

Final Time Complexity

Time Complexity: O(n)

This means the total work grows directly in proportion to the number of steps each Fiber performs.

Common Mistake

[X] Wrong: "Using Fibers makes the program run faster automatically."

[OK] Correct: Fibers help organize work cooperatively but do not reduce the total amount of work done; they just switch tasks without parallel speedup.

Interview Connect

Understanding how Fibers manage work step-by-step helps you explain cooperative multitasking and its impact on program flow and performance.

Self-Check

What if we added more Fibers running concurrently? How would the time complexity change?