Curry and partial application in Ruby - Time & Space Complexity

Time Complexity: Curry and partial application

O(n)

Understanding Time Complexity

When using curry and partial application, we want to know how the time to run the code changes as we give it more inputs.

We ask: How does the number of steps grow when we call the curried or partially applied function multiple times?

Scenario Under Consideration

Analyze the time complexity of the following Ruby code using curry and partial application.

add = ->(a, b, c) { a + b + c }
curried_add = add.curry
partial_add = curried_add.call(1)
result = partial_add.call(2).call(3)
    

This code creates a curried version of a function that adds three numbers, then partially applies the first argument, and finally calls the remaining arguments one by one.

Identify Repeating Operations

Look for repeated steps or calls in the code.

• Primary operation: Calling the curried function multiple times to supply arguments.
• How many times: Once per argument after currying (here, two calls after the first partial call).

How Execution Grows With Input

Each argument requires one function call after currying.

Input Size (n)	Approx. Operations
3 (arguments)	3 calls (one initial, two after)
10 (arguments)	10 calls (one initial, nine after)
100 (arguments)	100 calls (one initial, ninety-nine after)

Pattern observation: The number of calls grows linearly with the number of arguments supplied.

Final Time Complexity

Time Complexity: O(n)

This means the time to fully call a curried function grows in a straight line with the number of arguments.

Common Mistake

[X] Wrong: "Currying makes the function run faster because it breaks calls into smaller parts."

[OK] Correct: Currying changes how you call the function but does not reduce the total work; each argument still needs to be processed, so total time grows with the number of arguments.

Interview Connect

Understanding how currying affects time helps you explain function calls clearly and shows you can think about how code scales, a useful skill in many programming tasks.

Self-Check

What if we changed the curried function to accept all arguments at once instead of one by one? How would the time complexity change?