Time Complexity: Ractor for true parallelism
O(n / p)
0
0
Ractor for true parallelism in Ruby - Time & Space Complexity
Understanding Time Complexity
When using Ractors in Ruby, we want to understand how running code in parallel affects the total time it takes.
We ask: How does adding more Ractors change the work done and the time spent?
Scenario Under Consideration
Analyze the time complexity of this Ruby code using Ractors.
numbers = (1..1000).to_a
ractor1 = Ractor.new(numbers[0..499]) do |nums|
nums.map { |n| n * 2 }
end
ractor2 = Ractor.new(numbers[500..999]) do |nums|
nums.map { |n| n * 2 }
end
result1 = ractor1.take
result2 = ractor2.take
combined = result1 + result2
This code splits an array into two parts and processes each part in a separate Ractor to run in parallel.
Identify Repeating Operations
Look at what repeats and how often.
- Primary operation: Mapping over each half of the array to multiply numbers.
- How many times: Each Ractor processes about 500 elements once.
- Parallelism: Two Ractors run these operations at the same time.
How Execution Grows With Input
As the input size grows, the total work grows, but running in parallel changes how time adds up.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 multiplications split across 2 Ractors |
| 100 | 100 multiplications split across 2 Ractors |
| 1000 | 1000 multiplications split across 2 Ractors |
Pattern observation: Total operations grow linearly with input size, but time per Ractor depends on its share, potentially halving the time.
Final Time Complexity
Time Complexity: O(n / p)
This means the time grows linearly with input size but is divided by the number of Ractors (p) running in parallel.
Common Mistake
[X] Wrong: "Using more Ractors always makes the program run faster by the same amount."
[OK] Correct: Creating and communicating between Ractors has overhead, so adding too many can slow things down instead of speeding them up.
Interview Connect
Understanding how parallelism affects time helps you explain real-world performance improvements clearly and confidently.
Self-Check
What if we increased the number of Ractors to 10? How would the time complexity change?