Proc composition in Ruby - Time & Space Complexity

Time Complexity: Proc composition

O(n)

Understanding Time Complexity

We want to understand how the time needed changes when we combine multiple Procs (small pieces of code) in Ruby.

How does running one Proc after another affect the total work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

add_one = ->(x) { x + 1 }
double = ->(x) { x * 2 }

composed = ->(x) { double.call(add_one.call(x)) }

result = inputs.map(&composed) # assuming inputs is an array of size n
    

This code creates two simple Procs and then combines them so each input goes through both in order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calling each Proc once in sequence.
• How many times: Each Proc is called exactly one time per input.

How Execution Grows With Input

Each input value goes through both Procs one after the other, so the work grows by adding the cost of each Proc.

Input Size (n)	Approx. Operations
10	20 (10 inputs x 2 Procs each)
100	200 (100 inputs x 2 Procs each)
1000	2000 (1000 inputs x 2 Procs each)

Pattern observation: The total work grows directly with the number of inputs, multiplied by the number of Procs composed.

Final Time Complexity

Time Complexity: O(n)

This means the time grows in a straight line as the input size grows, because each input goes through a fixed number of Procs.

Common Mistake

[X] Wrong: "Composing Procs multiplies the time by the number of Procs squared."

[OK] Correct: Each input only passes through each Proc once, so the time adds up, it does not multiply in a more complex way.

Interview Connect

Understanding how combining small pieces of code affects performance helps you write clear and efficient programs, a skill valued in many coding challenges.

Self-Check

"What if we composed Procs inside a loop that runs n times? How would the time complexity change?"