Process forking for parallelism in Ruby - Time & Space Complexity

Time Complexity: Process forking for parallelism

O(n)

Understanding Time Complexity

When using process forking, we want to see how the program's running time changes as we create more child processes.

We ask: How does splitting work into parallel processes affect the total time spent?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    def parallel_work(tasks)
      pids = []
      tasks.each do |task|
        pid = Process.fork do
          task.call
          exit!
        end
        pids << pid
      end
      pids.each { |pid| Process.wait(pid) }
    end
    

This code runs a list of tasks in parallel by creating a new process for each task, then waits for all to finish.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop over each task to fork a process.
• How many times: Once per task, so as many times as tasks count.
• Secondary operation: Loop to wait for each child process to finish.
• Dominant operation: Forking processes for each task, since it starts parallel work.

How Execution Grows With Input

As the number of tasks grows, the program creates more processes, but they run at the same time.

Input Size (n)	Approx. Operations
10	10 forks + 10 waits, tasks run in parallel
100	100 forks + 100 waits, tasks run in parallel
1000	1000 forks + 1000 waits, tasks run in parallel

Pattern observation: The number of forks and waits grows linearly with tasks, but total time depends on longest task, not sum.

Final Time Complexity

Time Complexity: O(n)

This means the number of operations grows linearly with the number of tasks, but actual runtime can be much faster due to parallel execution.

Common Mistake

[X] Wrong: "Forking many processes always makes the program run n times faster."

[OK] Correct: Creating many processes adds overhead and system limits; also, tasks run in parallel but total time depends on the slowest task, not just number of tasks.

Interview Connect

Understanding how process forking affects time helps you explain parallelism clearly and shows you can think about real program performance beyond just code logic.

Self-Check

"What if we limited the number of child processes running at the same time? How would that change the time complexity?"